結果
| 問題 |
No.3298 K-th Slime
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-05 15:17:52 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,339 bytes |
| コンパイル時間 | 3,306 ms |
| コンパイル使用メモリ | 287,956 KB |
| 実行使用メモリ | 15,944 KB |
| 最終ジャッジ日時 | 2025-10-05 15:18:55 |
| 合計ジャッジ時間 | 14,681 ms |
|
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | WA * 14 TLE * 1 -- * 10 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using uc = unsigned char;
#define Max(X,Y) (((X) > (Y)) ? (X) : (Y))
#define Min(X,Y) (((X) < (Y)) ? (X) : (Y))
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define YES yes return 0;
#define NO no return 0;
#define pc cout << count << endl;
#define PC pc return 0;
#define INF 0x1fffffff
#define Eps LDBL_EPSILON
#ifdef DEBUG
#define dbg(X) cerr << X << endl
#else
#define dbg(...)
#endif
template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) noexcept {
if(!v.empty()) os << v[0];
for(size_t i = 1; i < v.size(); i++) os << " " << v[i];
return os;
}
template <typename T>
void swap(T& a, T& b) {
auto x = a;
a = b;
b = x;
}
template <typename T>
size_t partition(vector<T>& list, size_t start, size_t end) {
auto pivot = list[end-1];
auto hi = start;
for(auto i = start; i < end - 1; i++) {
if(list[i] <= pivot) {
swap(list[hi], list[i]);
hi++;
}
}
swap(list[hi], list[end-1]);
return hi;
}
template <typename T>
void quicksort(vector<T>& list, size_t l, size_t r) {
if(l < r) {
auto pivot = partition(list, l, r);
quicksort(list, l, pivot);
quicksort(list, pivot + 1, r);
}
}
struct string_set {
map<size_t, vector<string_view>> registry = {};
bool contains(string_view s) {
auto h = hash<string_view>()(s);
return registry.contains(h)
&& find(registry[h].begin(), registry[h].end(), s) != registry[h].end();
}
void add(string_view s) {
auto h = hash<string_view>()(s);
auto pos = find(registry[h].begin(), registry[h].end(), s);
if(pos != registry[h].end()) return;
registry[h].push_back(s);
}
void remove(string_view s) {
auto h = hash<string_view>()(s);
if(!registry.contains(h)) return;
auto pos = find(registry[h].begin(), registry[h].end(), s);
if(pos == registry[h].end()) return;
registry[h].erase(pos);
}
};
template <typename T>
struct BIT {
ll n;
vector<T> tree;
BIT(ll size) : n(size + 1), tree(n, 0) {}
void add(ll i, T x) {
for (ll idx = i; idx < n; idx += (idx & -idx)) {
tree[idx] += x;
}
}
T sum(ll i) {
T s(0);
for (ll idx = i; idx > 0; idx -= (idx & -idx)) {
s += tree[idx];
}
return s;
}
};
struct RSQ {
ll N;
vector<ll> tree;
RSQ(ll max) : N(), tree(max*4, 0) {
ll x = 1;
while(max > x) x*=2;
N = x;
}
void inc(ll i) {
i += N - 1;
tree[i]++;
while (i > 0) {
i = (i - 1) / 2;
tree[i]++;
}
}
ll find(ll k) {
auto [cod, num] = find_sect(k, 0);
if(cod) return num;
return -1;
}
pair<bool,ll> find_sect(ll k, ll n) {
if(n >= N-1) {
if(tree[n] < k) {
return {false, k - tree[n]};
}
return {true, n-N-1};
}
if(tree[n] < k) return {false, k - tree[n]};
auto [cod, num] = find_sect(k, 2*n+1);
if(cod) {
return {cod, num};
}
return find_sect(k-num, 2*n+2);
}
};
int main() {
cin.tie(nullptr);
ll N, K, Q;
cin >> N >> K >> Q;
vector<ll> A;
A.reserve(N+Q);
for(ll i = 0; i < N; i++) {
ll a;
cin >> a;
A.push_back(a);
}
sort(A.begin(), A.end());
for(; Q>0; Q--) {
int q;
cin >> q;
if(q == 1) {
ll x;
cin >> x;
A.push_back(x);
for(ll i = A.size()-1; i > 0; i--) {
if(A[i-1] > x) {
A[i] = A[i-1];
A[i-1] = x;
} else break;
}
} else if(q == 2) {
ll y;
cin >> y;
ll pl = A[K-1]+y;
for(ll i = K-1; i < A.size()-1; i++) {
if(A[i+1] < pl) {
A[i] = A[i+1];
A[i+1] = pl;
} else break;
}
} else {
cout << A[K-1] << endl;
}
}
}