結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2018-02-13 11:04:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 288 ms / 3,000 ms |
コード長 | 1,755 bytes |
コンパイル時間 | 843 ms |
コンパイル使用メモリ | 78,500 KB |
実行使用メモリ | 8,068 KB |
最終ジャッジ日時 | 2024-11-28 15:57:49 |
合計ジャッジ時間 | 6,033 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; /* BIT */ const int SIZE_B = 210000; //use bit[1] ~ bit[SIZE_B] struct BIT { int bit[SIZE_B+1]; BIT() { for (int i = 0; i <= SIZE_B; ++i) bit[i] = 0; } inline void add(int a, int x) { for (int i = a; i <= SIZE_B; i += i & -i) bit[i] = bit[i] + x; } inline int sum(int a) { int res = 0; for (int i = a; i > 0; i -= i & -i) res = res + bit[i]; return res; } }; /* 目的のデータ構造 */ struct SET { BIT bit; // 挿入 void insert(int num) { bit.add(num, 1); } // 削除 void erase(int num) { bit.add(num, -1); } // BIT 上の二分探索 int get(int k) { ++k; int res = 0; int N = 1; while (N <= SIZE_B) N *= 2; for (int i = N/2; i > 0; i /= 2) { if (res + i <= SIZE_B && bit.bit[res + i] < k) { k = k - bit.bit[res + i]; res = res + i; } } return res + 1; } }; /* 入力 */ int T[210000]; long long V[210000]; int main() { SET S; int Q, K; cin >> Q >> K; // クエリ先読み vector<long long> queries; for (int i = 0; i < Q; ++i) { cin >> T[i]; if (T[i] == 1) cin >> V[i], queries.push_back(V[i]); } // 座標圧縮 sort(queries.begin(), queries.end()); queries.erase(unique(queries.begin(), queries.end()), queries.end()); // クエリに答える for (int i = 0; i < Q; ++i) { if (T[i] == 1) { int index = lower_bound(queries.begin(), queries.end(), V[i]) - queries.begin(); ++index; // 1-index にする S.insert(index); } else { int size = S.bit.sum(SIZE_B); // S の要素数 if (K > size) { cout << -1 << endl; } else { int val = S.get(K-1); cout << queries[val - 1] << endl; S.erase(val); } } } }