문제

• 
• 시간 제한: 2초
• 메모리 제한: 192MB

Problem Analysis

Naive 하게 풀면, C(N, 2) 가지의 모든 경우를 비교하여 풀 수 있다. 그러나, 이는 시간 복잡도가 O(N^2)이다. 간단하게 두 번의 시험만 친다고 하면, 첫 시험에서 자신보다 잘 본 사람만 두 번째 시험 점수를 확인하면 된다. 이는 첫 번째 시험 기준으로 정렬하여, Segment Tree로 구간을 확인하여 풀 수 있다. 이를 시험 세 개로 확장하면 된다.

Algorithm

1. 첫 시험 순서로 정렬하여, 이를 segTree의 범위로 사용한다.
2. 두 번째 시험의 등수를, segTree의 값으로 사용한다.
3. 세 번째 시험 순서대로, 한 명씩 segTree에 추가하며, 조사한다.

• segTree에 현재 학생을 추가한다.
• 이때, 첫 시험에서 자신보다 등수가 높은 구간을 조사하여, 해당 구간에 학생이 존재하는지, 존재한다면 두 번째 시험의 등수는 어떤지 체크한다.

Data Structure

• segTree[]: 첫 시험의 등수를 범위로, value는 해당 구간에서의 두번 째 시험의 최고 등수로 한다.

결과

Other

시간 복잡도는

• segTree 생성에 O(N)
• 각 쿼리마다 O(logN)이다.