結果

問題 No.3298 K-th Slime
ユーザー syun0713
提出日時 2025-10-05 14:23:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 393 ms / 2,000 ms
コード長 3,929 bytes
コンパイル時間 2,282 ms
コンパイル使用メモリ 213,196 KB
実行使用メモリ 23,088 KB
最終ジャッジ日時 2025-10-05 14:24:05
合計ジャッジ時間 6,336 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#ifdef ATCODER
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
#endif
#ifdef ONLINE_JUDGE
#else
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
#endif
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
using ull = unsigned long long;
using vi = vec<int>;
using vs = vec<string>;
using si = set<int>;
using sll = set<ll>;
using vc = vec<char>;
using vvi = vec<vi>;
using vll = vec<ll>;
using vvll = vec<vll>;
using vsi = vec<si>;
using vsll = vec<sll>;
using vd = vec<double>;
using vvd = vec<vd>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using msi = map<string, int>;
using vpii = vec<pii>;
using vpll = vec<pll>;
using spii = set<pii>;
using spll = set<pll>;
using vb = vector<bool>;
using vvb = vector<vb>;
#define rep(i,j,n) for(ll i=j;i<n;i++)
#define rrep(i,j,n) for (ll i = n-1; i >=j; i--)
#define rp(i,n) rep(i,0,n)
#define rrp(i,n) rrep(i,0,n)
#define all(v) v.begin(), v.end()
#define pb push_back
#define ins insert
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl; 
#define yn(jg) cout<<(jg? "Yes":"No")<<endl;
#define NL {cout<<endl;}
#define n0 {cout<<"-1"<<endl;}
#define lwb lower_bound
#define upb upper_bound
#define sz size()
#define fi first
#define se second
#define nxp next_permutation
//lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
//S:中身型 op:左右合成 e:初期値
//F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない)
/*
using S = double;
using F = int;
S op(S a,S b) {
	return min(a, b);
}

S e() {
	return lmax;
}
S mapping(F x, S a) {//xをaに作用(x初期値に注意)
	if (x != 0)return x;
	else return a;
}
F composition(F f, F g) {//fの方が後(f初期値に注意)
	if (f != 0)return f;
	else return g;
}
F id() {return 0;}*/
//cout<<setprecision(15)<<fixed<<
//function<返り値の型(引数の型1, 引数の型2, ...)> 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) 
template<typename T1, typename T2>//keyの型、値の型
struct topk {
	multiset<pair<T2, T1>> top;
	multiset<pair<T2, T1>> bot;//昇順の時はgreaterを消す
	map<T1, T2> ktov;
	int k = 0;
	ll tsum = 0, asum = 0;
	void ar() {//個数整理
		while (top.size() > k) {
			auto it = top.end(); it--;
			bot.insert(*it);
			tsum -= it->fi;
			top.erase(it);
		}
		while (top.size() < k && bot.size() != 0) {
			auto it = bot.begin();
			top.insert(*it);
			tsum += it->fi;
			bot.erase(it);
		}
	}
	void set(int newk) {//最初に必ず呼ぶ
		k = newk;
		ar();
	}
	void erase(T1 a) {
		if (ktov.find(a) != ktov.end()) {
			auto b = ktov[a];
			if (top.find({ b,a }) != top.end()) {
				tsum -= b; asum -= b;
				top.erase({ b,a });
				ar();
			}
			else if (bot.find({ b,a }) != bot.end()) {
				asum -= b;
				bot.erase({ b,a });
				ar();
			}
			ktov.erase(a);
		}
	}
	void insert(T1 a, T2 b) {//兼update
		erase(a);
		ktov[a] = b;
		if (top.sz != 0 && (--top.end())->fi > b) {//昇順の時は>
			top.insert({ b,a });
			asum += b; tsum += b;
		}
		else {
			bot.insert({ b,a });
			asum += b;
		}
		ar();
	}
	void insert(pair<T1, T2> a) {
		insert(a.fi, a.se);
	}
	int bsum() {
		return asum - tsum;

	}
	auto find(T1 a) {
		return ktov.find(a);
	}
	T2 operator[](T1 a) {
		return ktov[a];
	}
};
int main() {
	int n, k, q;
	cin >> n >> k >> q;
	vll a(n); rp(i, n) cin >> a[i];
	topk<ll, ll> r;
	r.set(k);
	rp(i, n)r.insert(i, a[i]);
	while (q--) {
		ll x;
		cin >> x;
		if (x == 1) {
			ll y;
			cin >> y;
			a.pb(y);
			r.insert(ll(a.sz) - 1, y);
		}
		if (x == 2) {
			ll y; cin >> y;
			auto it = r.top.end();
			it--;
			y += it->first;
			ll b = it->second;
			r.erase(b);
			r.insert(b, y);
		}
		if (x == 3) {
			auto it = r.top.end();
			it--;
			cout << it->first << endl;
		}
	}
}
0