[AtCoder] ABC 170 E – Smart Infants

2020年9月11日2020年12月13日

問題

方針

ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、multiset を使って管理できるそうです。multiset は順序が保たれます。

ここで、幼稚園 \( i \) のレートの集合を \( S_i \) とし、各幼稚園の最大値の集合を \( T \) とします。まず初めに、\( N \) 人の幼稚園児の情報を \( S_i, T \) に反映させます。

幼稚園児 \( i \) が 幼稚園 \( c \) から \( d \) に転園するとして以下の処理を考えます。

転園処理

\( \max(S_c) = A_i\) のとき

\( T \) から \( A_i \) を削除します。さらに、\( S_c \) の中で \( A_i \) の個数が \( 1 \) かつ \( |S_c| \geq 2\) のとき、\( T \) に \( S_c \) の中で \( 2 \) 番目に大きい値を追加します。また、\(S_c \) から \( A_i \) を削除します。

\( \max(S_c) < A_i\) のとき

\( T \) から \( A_i \) を削除します。\( T \) に \( S_c \) の中で \( 2 \) 番目に大きい値を追加します。また、\(S_c \) から \( A_i \) を削除します。

上記以外のとき

\(S_c \) から \( A_i \) を削除します。

入園処理

\( |S_d| = 0 \) または \( \max(S_d) = A_i \)のとき

\( T \) に \( A_i \) を追加します。\( S_d \) に \(A_i \) を追加します。

\( \max(S_d) < A_i \) のとき

\( T \) から \( \max(S_d) \) を削除し、\( T \) に \( A_i \) を追加します。\( S_d \) に \(A_i \) を追加します。

また、入園処理と退園処理が終わったとき、幼稚園児の所属を更新します。

コード

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

int N, Q;
multiset<int> ms1[200000], ms2;
bool flag[200000]{};

int main() {
    cin >> N >> Q;
    int A[N], B[N], C[Q], D[Q];
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        B[i]--;
        ms1[B[i]].insert(A[i]);
    }
    
    for (int i = 0; i < N; i++) {
        if (ms1[B[i]].size() == 0) continue;
        if(flag[B[i]]) continue;
        int v = *ms1[B[i]].rbegin();
        for (int j = 0; j < ms1[B[i]].count(v); j++) {
            ms2.insert(v);
        }
        flag[B[i]] = true;
    }
    for (int i = 0; i < Q; i++) {
        cin >> C[i] >> D[i];
        C[i]--;
        D[i]--;
    }
    
    for (int i = 0; i < Q; i++) {
        int b = B[C[i]];
        if (*ms1[b].rbegin() == A[C[i]]) {
            ms2.erase(ms2.find(A[C[i]]));
            if (ms1[b].size() > 1 && ms1[b].count(A[C[i]]) == 1) {
                ms1[b].erase(ms1[b].find(A[C[i]]));
                ms2.insert(*ms1[b].rbegin());
            } else {
                ms1[b].erase(ms1[b].find(A[C[i]]));
            }
            
        } else if (*ms1[b].rbegin() < A[C[i]]){
            ms1[b].erase(ms1[b].find(A[C[i]]));
            ms2.insert(*ms1[b].rbegin());
            ms2.erase(ms2.find(A[C[i]]));
        } else {
            ms1[b].erase(ms1[b].find(A[C[i]]));
        }

        if (ms1[D[i]].size() == 0 || *ms1[D[i]].rbegin() == A[C[i]]) {
            ms2.insert(A[C[i]]);
        } else if (*ms1[D[i]].rbegin() < A[C[i]]) {
            ms2.insert(A[C[i]]);
            ms2.erase(ms2.find(*ms1[D[i]].rbegin()));
        }
        
        ms1[D[i]].insert(A[C[i]]);  
        B[C[i]] = D[i];
        cout << *ms2.begin() << "\n";

    }
    return 0;
}