CS Academy Min Races

リンク : https://csacademy.com/contest/archive/task/min-races/statement/

問題概要

N人のレーサーとK種類のクラスが存在する。数回のレースを行う。レーサーの勝利条件は自分より順位が高い人は自分より大きいクラスに属する人のみの場合勝利となる。N人の相対的な順位は確定していて、1レースに出場できる選手は選択できる。このとき、全員が一回以上優勝するのは最小で何回レースを行ったときか。

解説

相対順位は必ず守られるため、相対順位で最初にソートしておく。ソートした後のi番目の人のクラスをC_iとする。前から貪欲に決めていく時を考えると、C_i<C_j と i<j を満たす最小のjを順番に取っていけばよいとわかる。 一つ例を挙げると、下の図は、入力例4の場合の相対順位でソートした後にそれぞれのクラスを並べた。最初に赤を前から順に決め、次に青、緑と決めることである。 しかし、これではO(n²)かかるため間に合わない。そこで、i番目より順位の高いレーサーで、i番目のレーサーのクラス以上のレーサーが優勝する最小回数の次のレースにi番目のレーサーが優勝できることがわかる。そこで自身以上のレーサーについての それぞれのクラスの最小回数の最大 を考えることになる。範囲の最大なのでセグ木を使うことで高速化ができる。

LL n, k, ans;
Pll racer[220000];
Seg seg(220000);
int main() {
    cin >> n >> k;
    rep(i, n) {
        cin >> racer[i].second >> racer[i].first;
    }
    sort(racer, racer + n);
    rep(i, n) {
        LL x = seg.find(racer[i].second,k);
        ans = max(ans, x + 1);
        seg.update(racer[i].second, x + 1);
    }
    cout << ans << endl;
    return 0;
}