結果

問題 No.2809 Sort Query
ユーザー hiro1729
提出日時 2024-07-12 22:14:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,071 bytes
コンパイル時間 4,029 ms
コンパイル使用メモリ 259,984 KB
実行使用メモリ 34,688 KB
最終ジャッジ日時 2024-07-12 22:15:01
合計ジャッジ時間 14,540 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 5 TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main() {
	int N, Q;
	cin >> N >> Q;
	multiset<ll> A;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		A.insert(a);
	}
	// A[i]
	auto Ai = [&](int i) { auto d = A.begin(); advance(d, i); return *d; };
	multiset<ll> B, C;
	set<int> S;
	map<int, ll> d;
	while (Q--) {
		int t; cin >> t;
		if (t == 1) {
			int k; ll x; cin >> k >> x;
			k--;
			if (S.find(k) != S.end()) {
				B.erase(B.find(Ai(k)));
				C.erase(C.find(d[k]));
			}
			B.insert(Ai(k));
			C.insert(x);
			d[k] = x;
			S.insert(k);
		}
		if (t == 2) {
			for (ll i: B) {
				A.erase(A.find(i));
			}
			B.clear();
			for (ll i: C) {
				A.insert(i);
			}
			C.clear();
		}
		if (t == 3) {
			int k; cin >> k;
			k--;
			ll le = 1, ri = 1e18 + 1;
			while (le + 1 < ri) {
				ll mi = (le + ri) / 2;
				int c = distance(A.begin(), A.upper_bound(mi)) - distance(B.begin(), B.upper_bound(mi)) + distance(C.begin(), C.upper_bound(mi));
				if (c > k) {
					ri = mi;
				} else {
					le = mi;
				}
			}
			cout << ri << '\n';
		}
	}
}
0