BOJ 9034 - 순위

링크: https://www.acmicpc.net/problem/9034

오랜만의 포스팅. 아마 한동안 문제를 풀 시간은 없을 듯.. ㅠ

문제

매번 \(i\)번 선수에게 더해지는 점수가 주어지고, \(x\)번째 선수가 몇 등인지 실시간으로 출력하는 문제이다.

먼저 어떤 선수의 등수는 "그 선수보다 점수가 더 높은 사람의 수 + 1"이다.

매번 탐색을 하거나, 정렬을 한다면 \(100,000\)명의 선수에 대한 \(200,000\)번의 질의에 대답하기엔 시간상으로 버겁다.

내 등수는 구간 [내 점수 + 1, ∞)에 있는 사람의 수 + 1과 같다. 점수의 합은 최대 \(10^{9}\)이므로, 모든 점수를 압축할 필요가 있다.
이건 좌표압축 문제(BOJ 18870 - 좌표 압축)를 먼저 풀어보기를 권장한다.

점수가 더해질때마다, 이전의 내 점수 위치를 -1하고 새로 더해진 점수 위치를 +1하여 나중에 카운팅될 수 있도록 업데이트하면 된다.

코드