문제 정의

올해 대회에 n 팀(1번~n번 팀)이 참가하고, 우리 팀은 1번 팀이다.

각 팀의 점수는 푼 문제의 수 a와 각 문제의 페널티 합 b로 결정된다. 두 팀 $t_1$과 $t_2$가 있고 각 점수가 ($a_1$, $b_1$), ($a_2$, $b_2$) 일 때, $a_1 \gt a_2$ 또는 $a_1 = a_2$ 면서 $b_1 \lt b_2$ 이면 팀 $t_1$의 점수가 $t_2$의 점수가 높다. 어느 팀보다 점수가 높은 팀의 수 $k$이면, 그 팀의 등수는 $k + 1$이라고 한다.

최종 스코어보드 대신, 각 팀이 문제를 풀때마다 어느 팀이 문제를 풀었는지와 페널티가 주어진다. 각 문제 해결 이벤트마다 우리 팀의 등수를 출력한다.

아이디어

스코어보드(각 팀의 푼 문제 수, 페널티)와 우리 팀보다 높은 팀의 리스트를 유지하면서 단순한 방법으로 문제를 해결할 수 있었다.

다른 팀이 문제를 해결한 경우에는, 팀 순위가 우리 팀보다 높으면 우리 팀의 순위는 변함 없으므로 스코어보드만 갱신한다. 팀 순위가 우리 팀과 같거나 낮으면 스코어보드 갱신 후, 우리 팀보다 순위가 높아지면 우리 팀 보다 높은 팀의 리스트에 추가한다.

우리 팀이 문제를 해결한 경우에는, 스코어보드를 갱신 후, 우리 팀보다 높은 팀의 리스트를 하나씩 탐색하면서 우리 팀보다 점수가 낮아진 팀을 제거한다.

두 팀의 점수 비교는 두 번의 정수 비교만으로 가능하므로 $O(1)$, 우리 팀의 문제 해결시 선형 탐색은 $O(N)$의 시간복잡도를 가진다.

팀의 수 N의 최대 값은 100,000이고 문제 해결 이벤트의 수 M의 최대 값은 100,000이므로 선형 탐색이 M번 일어난다고 할 때, $N * M$은 100억이라는 값을 가진다. 일반적으로 1초당 10억 개 정도의 연산이 가능하다는 낭설을 고려하면 제한시간 5초 안에 해결하기 어려울 수 있다. 하지만 우리 팀의 문제 해결 시 선형 탐색은 모든 팀에 대해 일어나는 것이 아니며, 우리 팀의 문제 해결마다 $N$이 줄어들기 때문에 제한 시간 안에 충분히 해결 가능했다.

풀이

각 팀의 점수와 페널티를 유지하는 scoreboard 벡터, 점수 높은 팀의 리스트 higherTeamList, 우리 팀의 등수 myRank를 정의한다.

$t_2$팀이 $t_1$팀 보다 순위가 높은지 여부를 반환하는 함수 compare를 작성하여 사용한다.

각 문제 해결 이벤트마다 다른 팀이 문제를 해결한 경우, 팀 순위가 우리 팀보다 높으면 스코어보드만 갱신, 팀 순위가 우리 팀과 같거나 낮으면 우리보다 점수가 높아졌는지 확인한다.

우리 팀이 문제를 해결하면, 스코어보드 갱신 후, higherTeamList를 선형 탐색하면서 우리 팀보다 점수가 낮아진 팀을 제거한다.

코드

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int N, M;
int myRank = 1;
vector<int> higherTeamList;
vector<pair<int, int>> scoreboard;

int team, penalty;

// t2가 t1보다 순위가 높은지 여부 반환
bool compare(int t1, int t2)
{
    if (scoreboard[t1].first == scoreboard[t2].first)
        return scoreboard[t1].second > scoreboard[t2].second;
    else
        return scoreboard[t1].first < scoreboard[t2].first;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    scoreboard = vector<pair<int, int>>(N + 1);

    for (int m = 0; m < M; m++)
    {
        cin >> team >> penalty;

        if (team != 1) {
            // 다른 팀이 문제를 해결한 경우
            if (compare(1, team)) {
                // team의 순위가 우리 팀보다 높으면
                scoreboard[team].first += 1;
                scoreboard[team].second += penalty;
            }
            else {
                // team의 순위가 우리 팀과 같거나 낮으면
                scoreboard[team].first += 1;
                scoreboard[team].second += penalty;
                if (compare(1, team)) {
                    higherTeamList.push_back(team);
                    myRank += 1;
                }
            }
        }
        else {
            // 우리 팀이 문제를 해결한 경우
            scoreboard[1].first += 1;
            scoreboard[1].second += penalty;

            auto it = higherTeamList.begin();
            for (; it != higherTeamList.end();)
            {
                if (!compare(1, *it)) {
                    it = higherTeamList.erase(it);
                    myRank -= 1;
                }
                else it++;
            }
        }
        cout << myRank << '\n';
    }
    return 0;
}

결과