結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
|
提出日時 | 2023-02-04 00:45:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 3,000 ms |
コード長 | 3,172 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 177,892 KB |
実行使用メモリ | 9,860 KB |
最終ジャッジ日時 | 2024-07-02 22:37:05 |
合計ジャッジ時間 | 5,062 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() using ll = long long; template <typename T> // 内部では1-baseですが、外からは0-baseに見せてます struct fenwickTree { public: fenwickTree(int size) : _size(size), data(size + 1, 0) { // sizeを超えない2べきを求めておく(lowerBound用) beki_floor = 1; while(beki_floor <= _size / 2) { beki_floor <<= 1; } } // a[index] += x を行う void add(int index, T x) { assert(0 <= index && index < _size); int curIndex = index + 1; while(curIndex <= _size) { data[curIndex] += x; // 区間の長さ分だけ番号に足したところを更新していく curIndex += curIndex & (-curIndex); } } // a[left] + ... + a[right - 1] を求める T sum(int left, int right) const { assert(0 <= left && left < right && right <= _size); return sumFromFirst(right) - sumFromFirst(left); } // a[0] + ... a[x] >= w なる最小のxを求める(なければx = _size) int lowerBound(int w) const { if(w <= 0) return 0; int x = 0; for(int k = beki_floor; k > 0; k /= 2) { if(x + k <= _size && data[x + k] < w) { w -= data[x + k]; x += k; } } return x; } private: int _size; vector<T> data; // 1-base int beki_floor; // _size以下の最大の2べき // a[0] + ... a[right - 1] の和を求める T sumFromFirst(int right) const { assert(0 <= right && right <= _size); if(right == 0) { return 0; } T ans = 0; int curIndex = right; while(curIndex > 0) { ans += data[curIndex]; // 次に足すべき区間は番号から区間の長さだけ引いたもの curIndex -= curIndex & (-curIndex); } return ans; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int q, k; cin >> q >> k; vector<ll> input(q); // -1ならクエリ2 for(int i = 0; i < q; i++){ int t; cin >> t; if(t == 1){ cin >> input[i]; } else{ input[i] = -1; } } // 入力のうちクエリ1のものを取り出す vector<pair<ll, int>> query1; for(int i = 0; i < q; i++){ if(input[i] == -1) continue; query1.emplace_back(input[i], i); } // 座標圧縮 sort(ALL(query1)); for(int i = 0; i < query1.size(); i++){ input[query1[i].second] = i; } const int maxQuery1 = 200'000; fenwickTree<ll> BIT(maxQuery1); for(int i = 0; i < q; i++){ // クエリ1 if(input[i] != -1){ BIT.add(input[i], 1); } // クエリ2 else { if(BIT.sum(0, maxQuery1) < k) cout << -1 << "\n"; else{ int ansIndex = BIT.lowerBound(k); cout << query1[ansIndex].first << "\n"; BIT.add(ansIndex, -1); } } } }