結果
| 問題 |
No.3298 K-th Slime
|
| コンテスト | |
| ユーザー |
mele
|
| 提出日時 | 2025-10-05 14:52:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,083 bytes |
| コンパイル時間 | 1,893 ms |
| コンパイル使用メモリ | 196,288 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-10-05 14:53:41 |
| 合計ジャッジ時間 | 4,135 ms |
|
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 6 WA * 19 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FFOR(i,a,b) for (ll i = (b); i >= (a); i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) FFOR(i,0,n)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;
const int MOD = 100000000;
class fenwick_tree_set {
const int n;
int cnt;
vector<int> data;
int find(int p) const {
int res = 0;
while (p > 0) {
res += data[p];
p -= p & -p;
}
return res;
}
void add(int p, int x) {
++p;
while (p <= n) {
data[p] += x;
p += p & -p;
}
}
public:
fenwick_tree_set(int maxi)
: n(maxi + 1), cnt(0), data(n + 1) {}
int size() const {
return cnt;
}
int count(int val) const {
return find(val + 1) - find(val);
}
void insert(int val) {
add(val, 1);
cnt += 1;
}
void erase(int val) {
add(val, -1);
cnt -= 1;
}
int kth_element(int k) const {
int p = 1 << (32 - __builtin_clz(n)), res = 0;
while (p >>= 1) {
if (res + p <= n && data[res + p] <= k) {
k -= data[res + p];
res += p;
}
}
return res;
}
};
int main(){
int N,K,Q,q,x,a;
cin>>N>>K>>Q;
fenwick_tree_set f(N);
rep(i,N){
cin>>a;
f.insert(a);
}
rep(i,Q){
cin>>q;
if(q==1){
cin>>x;
f.insert(x);
}else if(q==2){
cin>>x;
int kk = f.kth_element(K-1);
f.erase(kk);
f.insert(kk+x);
}else{
int kk = f.kth_element(K-1);
cout<<kk<<endl;
}
}
return 0;
}
mele