結果
問題 | 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-baseint 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ならクエリ2for(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++){// クエリ1if(input[i] != -1){BIT.add(input[i], 1);}// クエリ2else {if(BIT.sum(0, maxQuery1) < k) cout << -1 << "\n";else{int ansIndex = BIT.lowerBound(k);cout << query1[ansIndex].first << "\n";BIT.add(ansIndex, -1);}}}}