読者です 読者をやめる 読者になる 読者になる

Codeforces Round #388 (Div. 2) D. Leaving Auction

問題

codeforces.com

考察

人が消えるオークションをする問題です。
注意点として、間の人が消えてある人が連続したら、その場合は圧縮されて落札可能な最も安い値段になります。

参加者の数もクエリの数も 2 * 10^{5}と多いですが、 除外する参加者の数が最大 2 * 10^{5}なので、比較的シンプルな方法で間に合います。

条件

  • 人が指定された時、まとめて除外できる
  • 残っている人の中で、最大の落札価格を出した人がわかる
  • 最大の落札価格を出した人の価格一覧と、その次の人の価格一覧がわかる
    • これは間の人が消えていた場合に対処するためです

これらを満たせば良いので、([その人の最大価格], [その人の価格一覧]) を登場した人の分だけ持ち、二分木で大きい方が上に来るように持てばよいです。
C++だと、mapのソート順を変えるとうまくいきます。

また、同じ価格を出す人はいないので、価格から人を決定することができます。

手順

  • 前述のデータを作る( O(n)
  • クエリの処理( O(q)
    • 指定された人を消す( O(k * logn)
    • 最大の落札価格の人(A)、次の人(B)を取り出す( O(1)
    • Bの最大価格を上回るAの価格を二分探索して決める( O(logn)
    • 出力
    • 消された人を戻す( O(k * logn)

残っている人がいない場合や1人しか残っていない場合は分ける必要がありますが、 簡単に処理できます。

全体として O(q * logn+ k * logn)程度で処理ができ、間に合わせることができます。

注意

方針としては上記で良いですが、これだとTLEを食らって間に合いませんでした。

そこで、
set<([その人の最大価格], [その人の番号])> (大きい順)
vector[その人の番号] = [その人の価格一覧]
とデータを分けると上手く行ってくれました。
復元処理で時間がかかったのでしょうか。

また、cin/coutでも通りましたが、危ういのでscanf/printfにした方が無難です。

コード

int main() {
    int n;
    cin >> n;

    unordered_map<int, int> bid_num;
    vi mx_bid(n, 0);
    vvi tmp(n);
    set<pii, greater<pii>> member;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        --a;
        tmp[a].push_back(b);
        bid_num[b] = a;
        chmax(mx_bid[a], b);
    }

    rep(i, n) {
        if (!tmp[i].empty()){
            member.insert(mp(mx_bid[i], i));
        }
    }

    int q;
    cin >> q;
    while(q--) {
        int k;
        cin >> k;

        vi remove_list(k);
        rep(i, k) {
            int l;
            cin >> l;
            --l;
            remove_list[i] = l;
        }

        // remove
        tr(it, remove_list) {
            int bid = mx_bid[*it];
            member.erase(mp(bid, *it));
        }

        // check
        if(member.empty()) {
            cout << "0 0" << endl;
        }
        else if(member.size() == 1) {
            pii res = *member.begin();
            cout << res.second + 1 << " " << tmp[res.second][0] << endl;
        }
        else {
            auto res1 = *member.begin();
            auto res2 = *(++member.begin());
            int mx = tmp[res2.second].back();
            int t = *lower_bound(all(tmp[res1.second]), mx);
            cout << res1.second + 1 << " " << t << endl;
        }

        // back
        tr(it, remove_list) {
            if(!tmp[*it].empty())
                member.insert(mp(mx_bid[*it], *it));
        }
    }

    return 0;
}

感想

コードが汚くてゴリ押しした感がありますが、通ったので良しとします。