Coci
레이팅 미적용의견: 0
\(3^{rd}\) round, November \(29^{th}\), 2014
The \(3^{rd}\) round of COCI is already here! In order to bet on predict the scores, we have assumed the following:
• If contestant A scored strictly more points than contestant B in each of the first two rounds, then in the
third round A will score at least an equal amount of points as B.
Of course, in each round (including this one, the 3rd one) it is possible to score from 0 to 650 points. On the
total ranking list, contestants are sorted descending according to the sum of points from all three rounds.
The contestants with an equal sum share the same place and the next contestant gets the realistic following place.
For example, contestants with sums equal to 1000, 1000, 900, 900 and 800 points win places 1., 1., 3., 3. and 5.,
respectively.
For each of the N contestants, we know the number of points scored in the first and second round. Given the
aforementioned assumption, determine the highest and lowest place each contestant can get on the total ranking
list after three rounds of COCI.
The first line of input contains an integer N (1 ⩽N ⩽500 000), the number of contestants.
Each of the following N lines contains two integers from the interval [0, 650]: the number of points each contestant
won in the first and second round.
For each contestant, in the order given in the input, output two integers per line: the required highest and lowest
place they can get on the total ranking list.
5
250 180
250 132
220 123
132 194
220 105
10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456output
1 3
1 3
3 5
1 5
3 5
1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10평가 및 의견
Coci
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Coci