[AtCoder] ABC 170 E – Smart Infants
問題
方針
ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、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; }
ディスカッション
コメント一覧
まだ、コメントがありません