結果
問題 |
No.3298 K-th Slime
|
ユーザー |
|
提出日時 | 2025-10-05 13:42:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 84 ms / 2,000 ms |
コード長 | 4,097 bytes |
コンパイル時間 | 1,985 ms |
コンパイル使用メモリ | 209,588 KB |
実行使用メモリ | 11,076 KB |
最終ジャッジ日時 | 2025-10-05 13:42:37 |
合計ジャッジ時間 | 3,865 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct SplitMultiset2{ //上位(下位)K個とそれ以外に分ける. //削除クエリがないならpriorityqueueで簡潔&定数倍改善. private: int siz,K; bool Max; multiset<long long> L,R; long long val,ex; //val->min(siz,K)個の和,ex->範囲外の和,Max->大きい方が偉い?; //L->K個採用集合,R->不採用集合. //構築O(|A|log|A|),クエリO(logsiz). public: template<typename T> SplitMultiset2(int k,bool M,vector<T> A){ K = k; siz = A.size(); Max = M; val = 0; ex = 0; sort(A.begin(),A.end()); long long inf = numeric_limits<long long>::max(); if(Max){ if(siz <= K){ L = multiset<long long>(A.begin(),A.end()); for(auto &a : A) val += a; } else{ L = multiset<long long>(A.begin()+siz-K,A.end()); R = multiset<long long>(A.begin(),A.begin()+siz-K); for(int i=0; i<siz-K; i++) ex += A.at(i); for(int i=siz-K; i<siz; i++) val += A.at(i); } L.insert(inf); R.insert(-inf); } else{ if(siz <= K){ L = multiset<long long>(A.begin(),A.end()); for(auto &a : A) val += a; } else{ L = multiset<long long>(A.begin(),A.begin()+K); R = multiset<long long>(A.begin()+K,A.end()); for(int i=0; i<K; i++) val += A.at(i); for(int i=K; i<siz; i++) ex += A.at(i); } L.insert(-inf); R.insert(inf); } } SplitMultiset2(int k,bool M):siz(0),K(k),Max(M),val(0),ex(0){ long long inf = numeric_limits<long long>::max(); if(Max) L = {inf},R = {-inf}; else L = {-inf},R = {inf}; } void add(long long x){ //xを追加する siz++; if(siz <= K){ //K個以下なら採用. val += x; L.insert(x); return; } if((Max && *L.begin() >= x)||(!Max && *L.rbegin() <= x)){ ex += x; R.insert(x); return; } val += x; L.insert(x); if(Max){ long long v = *L.begin(); ex += v; val -= v; R.insert(v); L.erase(L.begin()); } else{ long long v = *L.rbegin(); ex += v; val -= v; R.insert(v); L.erase(--L.end()); } } void erase(long long x){ //xを削除する xは存在しなければならない. siz--; if(siz < K){ //K個以下なら絶対消える. val -= x; L.erase(L.find(x)); return; } auto itr = R.find(x); if(itr != R.end()){ ex -= x; R.erase(itr); return; } itr = L.find(x); assert(itr != L.end()); val -= x; L.erase(itr); if(Max){ long long v = *R.rbegin(); val += v; ex -= v; L.insert(v); R.erase(--R.end()); } else{ long long v = *R.begin(); val += v; ex -= v; L.insert(v); R.erase(R.begin()); } } long long Kth(){ //K番目を返す. assert(siz >= K); if(Max) return *L.begin(); else return *L.rbegin(); } long long sum(){return val;} //採用の和を返す. long long qwerty(){return ex;} //不採用の和 要る?これ 雑魚命名してます. int size(){return siz;} //要素数を返す. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,K,Q; cin >> N >> K >> Q; vector<long long> A(N); for(auto &a : A) cin >> a; SplitMultiset2 Z(K,false,A); while(Q--){ int t; cin >> t; if(t == 3) cout << Z.Kth() << "\n"; else if(t == 1){ int x; cin >> x; Z.add(x); } else{ long long y; cin >> y; long long v = Z.Kth(); Z.erase(v),Z.add(v+y); } } }