データ構造を用いたシュミレーションの高速化問題．
\(1 \leq a_{i} \leq 2\) と小さいので，そこから考える． 簡単のため， まずは\(a_{i} = 1\) で考える．
最大値を高速に求める必要がある． 消費期限はすべて異なるので，set型で実現できる． 最大を削除するのは，\(O(log N)\) でできる． ただし，削除だけでなく補充もしないといけないので， どの列から削除したのか，index も取得したい．
方法として考えられるのは，
今回は後者で実装する．
補充する候補をqueue で管理しておく．
\(q_{i} := i 列目に補充する候補\)
とする．
\(a_{i} = 2\)の場合も同様．
\(s_{j} := 前からj番目の商品の消費期限全体の集合\)
とする． あとは購入と補充を実装すればよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vvll v(2, vll(n)); // rem : v[0][j] は使わない
map<ll,int> mp;
rep(i,n){
ll k ; cin >> k;
rep(j,k){
ll t; cin>> t;
q[i].push(t);
mp[t] = i;
}
q[i].push(-INFL);
q[i].push(-INFL);
}
ll m; cin >> m;
vll a(m); rep(i,m) cin >> a[i];
rep(i,2){
rep(j,n){
st[i].insert(q[j].front());
v[i][j] = q[j].front();
q[j].pop();
}
}
auto update1 = [&](ll x, ll ind) -> ll {
st[1].erase(x);
st[1].insert(q[ind].front());
v[1][ind] = q[ind].front();
q[ind].pop();
return x;
};
auto update0 = [&](void) -> ll {
auto it = st[0].end(); it--;
ll ma = *it;
int ind = mp[ma];
ll x = v[1][ind];
st[0].erase(ma);
st[0].insert(x);
update1(x, ind);
return ma;
};
rep(i,m){
if(a[i] == 1){
cout << update0() << endl;
}else{
auto it0 = st[0].end(); it0--;
auto it1 = st[1].end(); it1--;
ll ma = max(*it0, *it1);
int ind = mp[ma];
if(*it0 > *it1) update0();
else update1(ma, ind);
cout << ma << endl;
}
}
return 0;
}
