問題概要

文字列を投稿すると得点が与えられるコンテストに、 $N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ がこの順に投稿され、それぞれ $T_{1}, T_{2}, \dots, T_{N}$ 点が与えられた。

各文字列は、過去に同じ文字列が投稿されていないとき、オリジナルであるという。オリジナルな投稿文字列のうち、最多得点を獲得したものが何番目に投稿されたものであるかを答えよ（タイがある場合はそのうちの最も早いもの）。

制約

$1 \le N \le 10^{5}$

考えたこと

最初は、map を使って、各文字列のオリジナルの得点と、オリジナルの投稿順を整理することを考えた。それでも解けるが、もっと簡単に解ける。

単純に次のように考えればよい。

$T_{i}$ が最大となる $i$ （タイがあればそのうちの最小値）を求めよ。

ただし、 $S_{i}$ がオリジナルではないような $i$ は除く。

$S_{i}$ がオリジナルではないような $i$ は除くためには、set<string> 型が使える。全体の計算量は $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, T;
    string S;
    cin >> N;
    int max_score = 0, res;
    set<string> already;
    for (int i = 0; i < N; i++) {
        cin >> S >> T;
        if (already.count(S)) continue;
        already.insert(S);

        if (max_score < T) {
            max_score = T;
            res = i;
        }
    }
    cout << res+1 << endl;
}