프로그램 명: coci_coci
제한시간: 1 초
COCI의 3차 시험이 곧 시작된다. 학생들의 점수를 편하게 예측하기 위해, 아래 제약을 넣자.
- 만약 학생 A가 1, 2차 시험에서 학생 B보다 높은 점수를 받았다면 3차 시험에서는 A가 최소한 B의 점수 이상을 받는다.
각 시험마다, 학생들은 0점 이상 650점 이하의 점수를 받는다. 학생들의 최종 순위는 세 번의 시험 점수의 합이 높은 순으로 결정한다. 만약 다섯 학생들의 점수의 합이 1000, 1000, 900, 900, 800점이라면 이들의 순위는 1, 1, 3, 3, 5등이다.
당신은 N명의 학생들의 1, 2차 시험 점수를 갖고 있다. 이를 이용해서 각 학생의 순위로 가능한 범위를 구하여라.
입력 형식
-
첫 번째 줄에는 학생의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
-
두 번째 줄부터 N개의 줄에는 각 학생의 1차 시험 점수와 2차 시험 점수에 해당되는 0 이상 650 이하의 두 정수가 주어진다.
출력 형식
첫 번째 줄부터 N개의 줄에 각 학생의 최대 순위와 최소 순위를 출력한다.
입출력 예
입력
5
250 180
250 132
220 123
132 194
220 105
출력
1 3
1 3
3 5
1 5
3 5
입력
10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456
출력
1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10
The 3rd 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
출력
1 3
1 3
3 5
1 5
3 5
입력
10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456
출력
1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10
출처:coci 2013/2014 4/6
번역:functionx
[질/답]
[제출 현황]
[푼 후(0)]