コンテンツにスキップ

競プロキャンプ2026関西 E - Join Wars

サイト
MOFE
コンテスト
競プロキャンプ2026関西
問題
E - Join Wars

NN 人のプレイヤーと MM 個のインスタンスがあり、インスタンス ii の定員は AiA_i です。満員のインスタンスに入ろうとしたプレイヤーは、そのインスタンスの待機列の最後尾に並びます。次の 2 種類のクエリを合わせて QQ 個処理する問題です(1≤N,M,Q≤5×1051 \le N, M, Q \le 5 \times 10^5)。

  • 1 x y:プレイヤー xx が今の居場所を離れ、インスタンス yy に入ろうとする。インスタンスから退出した場合は、そのインスタンスの待機列の先頭のプレイヤーが入場する。待機列に並んでいた場合は、列から外れる。
  • 2 z:プレイヤー zz がインスタンス pp に入場していれば 1 p、インスタンス pp の待機列に並んでいれば 2 p、どちらでもなければ -1 を出力する。

インスタンスごとに、入場しているプレイヤーの集合と、待機列を管理して、書かれているとおりにシミュレーションします。

待機列では、先頭(最も早く並んだプレイヤー)を取り出す操作のほかに、途中のプレイヤーが抜ける操作があります。そのため、通常のキューではなく、(並んだ時刻, プレイヤー) の組を入れた順序付き集合(C++ の std::set)で管理します。集合の最小の要素が待機列の先頭です。

クエリ 1 では、まずプレイヤー xx を今いる場所から取り除きます。インスタンスから退出した場合は、空いた枠に待機列の先頭を入場させます。続けて、xx をインスタンス yy の待機列の最後尾に入れてから、定員に空きがある間は待機列の先頭を入場させます。yy に空きがあれば、待機列は空のはずなので、xx がそのまま入場することになります。

各プレイヤーについて、今いるインスタンスの番号と、並んだ時刻を記録しておきます。こうすると、集合から取り除くときの要素も、クエリ 2 で待機列にいるかどうかも、O(log⁡N)O(\log N) で分かります。全体の計算量は O(M+Qlog⁡N)O(M + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, Q);
VL(A, M);
vec<set<pl>> room(M), que(M);
vl idx(N, -1);
vl tm(N, -1);
rep(i, Q) {
LL(q);
if (q == 1) {
LL(x, y);
x--, y--;
ll &z = idx[x];
if (z >= 0) {
if (room[z].contains({tm[x], x})) {
room[z].erase({tm[x], x});
while (len(room[z]) < A[z] && len(que[z])) {
room[z].insert(que[z].extract(min(que[z])));
}
} else {
que[z].erase({tm[x], x});
}
}
tm[x] = i;
z = y;
que[z].insert({i, x});
while (len(room[z]) < A[z] && len(que[z])) {
room[z].insert(que[z].extract(min(que[z])));
}
} else {
LL(z);
z--;
if (idx[z] >= 0) {
print(1 + que[idx[z]].contains({tm[z], z}), idx[z] + 1);
} else {
print(-1);
}
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

room[z] がインスタンス z に入場しているプレイヤーの集合、que[z] が待機列です。どちらも要素は (インスタンス z に入ろうとしたクエリの番号, プレイヤー) の組です。idx[x] はプレイヤー x がいるインスタンス(どこにもいなければ −1-1)、tm[x] は最後にクエリ 1 で動いたときのクエリの番号です。z は idx[x] への参照なので、z = y で idx[x] が更新されます。

min(que[z]) は待機列の先頭の要素で、extract で que[z] から取り出し、そのまま room[z] に入れています。クエリ 2 では、que[idx[z]] に入っていれば待機列、そうでなければ入場中です。

使用ライブラリ:cpp_include@9c33ee7