CODEFORCE 246 Div.2 B题

Love The Way You Lie 2022-03-31 08:36 200阅读 0赞

题目例如以下：

B. Football Kit

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Consider a football tournament where *n* teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the *i*\-th team has color *x**i* and the kit for away games of this team has color *y**i* (*x**i* ≠ *y**i*).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (*n*(*n* - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.

Input

The first line contains a single integer *n* (2 ≤ *n* ≤ 105) — the number of teams. Next *n* lines contain the description of the teams. The *i*\-th line contains two space-separated numbers *x**i*, *y**i* (1 ≤ *x**i*, *y**i* ≤ 105; *x**i* ≠ *y**i*) — the color numbers for the home and away kits of the *i*\-th team.

Output

For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.

Sample test(s)

Input

2
    1 2
    2 1

Output

2 0
    2 0

Input

3
    1 2
    2 1
    1 3

Output

3 1
    4 0
    2 2

刚開始用双重循环查找超时了，最后改为二分查找AC。

代码例如以下：

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #429 (Div. 2) B. Godsend

[Problem - B - Codeforces][] 题意：给定一个数列，先手可以remove一段区间和为奇数的区间，后手可以remove一段区间和为偶数的区间，问你

落日映苍穹つ/ 2024年03月30日 12:48/ 0 赞/ 93 阅读

相关 Codeforces Round #572 (Div. 2)B

B. Number Circle 题目链接：[http://codeforces.com/contest/1189/problem/B][http_codeforces.

小灰灰/ 2023年08月17日 15:40/ 0 赞/ 173 阅读

相关 Codeforces Round #688 (Div. 2) A，B

A Cancel the Trains [传送门][Link 1] 题目大意有 100 个从下向上的火车道，100 个从左向右的火车道，如图所示 ![车

╰半夏微凉°/ 2022年12月26日 11:16/ 0 赞/ 160 阅读

相关 Codeforces Round #663 (Div. 2) B题

[题目链接][Link 1] include <cstdio> include <iostream> using namespace std

àì夳堔傛蜴生んèń/ 2022年11月26日 07:38/ 0 赞/ 192 阅读

相关 Codeforces 246B-Increase and Decrease【模拟】

B. Increase and Decrease time limit per test 2 seconds memory limit per test 256 meg

以你之姓@/ 2022年08月21日 13:42/ 0 赞/ 32 阅读

相关 codeforce 246B——Good Sequences

第一次的尝试的思路是，用dp进行进行搜索，不过在第21组TLE，这也很正常。因为为复杂度是O(n^2),而n的最大值为为10^5. 第二次尝试把所给的数进行素性拆分、定

矫情吗；*/ 2022年08月11日 04:58/ 0 赞/ 206 阅读

相关 CODEFORCE 246 Div.2 B题

题目例如以下： B. Football Kit time limit per test 1 second memory limit per test 256 mega

Love The Way You Lie/ 2022年03月31日 08:36/ 0 赞/ 201 阅读

相关 Codeforces Round #541 (Div. 2) B.Draw!

链接：https://codeforces.com/contest/1131/problem/B 题意：给n次足球比分，求存在平局的机会。思路：结构体

今天药忘吃喽~/ 2021年12月23日 11:29/ 0 赞/ 265 阅读

相关 Codeforces Round #568 (Div. 2)B

B. Email from Polycarp 题目链接：[http://codeforces.com/contest/1185/problem/B][http_codef

Myth丶恋晨/ 2021年12月03日 22:43/ 0 赞/ 271 阅读

相关 codeforces 278Div1 B题

虚拟参赛的时候没想到是线段树，看到很多人都过了，也蛮着急的。首先用二分+线段树的方法更新DP\[i\]：它表示以A\[i\]为结尾可以最前到哪个位置；再用线段树计算an

痛定思痛。/ 2021年10月23日 07:23/ 0 赞/ 260 阅读