SRM 679 Div2 Medium

TopCoder Statistics - Problem Statement

• 復習。復習。
• 問題文の意味がわからなくてタイムロスしてしまった。
• ある時間での勝者を探す。時間の範囲は 0~10^9 なので単純なループじゃ TLE するが、各 submit time とその前後 1 秒くらいだけ調べればよいので 3*n のループで済む。
• submit 数がどれくらなのかがちょっとわからないので、累積和を事前に計算して、二分探索によって高速化しておく。
• 本番時間ギリギリでサンプル通してサブミットしたのに system test で落ちた...。
• 原因は time == 0 のときの累積和計算を push_back していなかったから。
• 区間端のコーナーケースの処理忘れをしないように注意しよう。もったいなさすぎる。

class ContestScoreboard {
public:
vector <int> findWinner(vector <string> scores) {
        int n = scores.size();
        vector<ll> ret(n,0);
        vector<string> names(n);
        vector<vector<pair<ll,ll>>> sbm(n); //
        vector<vector<pair<ll,ll>>> sum(n);

        vector<ll> time;
        // O(n)
        REP(i,n)
        {
            auto tokens = split(scores[i], " ");
            names[i] = tokens[0];
            FOR(j,1,tokens.size())
            {
                auto v = split(tokens[j],"/");
                ll t,val;
                t = stoll(v[1]);
                val = stoll(v[0]);
                sbm[i].emplace_back(t,val); //sort by time
                // 探索対象となる時間は submit time とその前後 1 秒くらいでよい
                time.push_back(max(t-1,0LL));
                time.push_back(t);
                time.push_back(max(t+1,0LL));
            }
            sort(RANGE(sbm[i]));
            // 累積和を計算しておく
            ll s = 0;
            sum[i].emplace_back(0,0); // time == 0 のときを入れないとダメ
            REP(j,sbm[i].size())
            {
                ll t,v;
                tie(t,v) = sbm[i][j];
                s += v;
                sum[i].emplace_back(t,s);
            }
        }
        // 重複時間削除
        sort(RANGE(time));
        time.erase(unique(time.begin(), time.end()), time.end());

        // O(n*3 * n * log(m))
        vector<int> win(n,0);
        for (auto T : time)
        {
            int maxj = -1;
            string maxName="$";
            ll maxScore = -1;
            REP(i,n)
            {
                auto idx = lower_bound(RANGE(sum[i]),make_pair(T,-1LL)) - sum[i].begin();

                if (idx == 0)
                    continue;

                ll val;
                tie(ignore,val) = sum[i][idx-1];

                if ( val > maxScore || (val == maxScore && names[i] <  maxName))
                {
                    maxj = i;
                    maxName = names[i];
                    maxScore = val;
                }
            }
            if (maxj >= 0)
                win[maxj] = 1;
        }
        return win;
}
};