結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
|
提出日時 | 2024-11-30 14:00:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 3,000 ms |
コード長 | 2,281 bytes |
コンパイル時間 | 2,916 ms |
コンパイル使用メモリ | 255,992 KB |
実行使用メモリ | 10,040 KB |
最終ジャッジ日時 | 2024-11-30 14:00:35 |
合計ジャッジ時間 | 6,593 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#ifndef LOCAL #include <bits/stdc++.h> using namespace std; #define debug(...) (void(0)) #else #include "algo/debug.h" #endif template <class T> struct FenwickTree { private: int n; int pw; std::vector<T> dat; public: FenwickTree(int m = 0) { init(m); } void init(int m) { n = m; pw = std::bit_floor((unsigned int)n); dat.assign(n, T{}); } void add(int p, const T& x) { assert(0 <= p && p < n); for (p += 1; p <= n; p += p & -p) { dat[p - 1] += x; } } T sum(int l, int r) const { assert(0 <= l && l <= r && r <= n); return sum(r) - sum(l); } int select(T x) const { int at = 0; for (int len = pw; len > 0; len >>= 1) { if (at + len <= n && dat[at + len - 1] <= x) { at += len; x -= dat[at - 1]; } } assert(0 <= at && at <= n); return at; } private: T sum(int r) const { T ans{}; for (; r > 0; r -= r & -r) { ans += dat[r - 1]; } return ans; } }; void solve() { int Q, K; cin >> Q >> K; FenwickTree<int64_t> fw(Q); vector<pair<int, int64_t>> Qs(Q); vector<int64_t> cc; for (int i = 0; i < Q; i++) { int64_t o, v = -1; cin >> o; if (o == 1) { cin >> v; cc.push_back(v); } Qs[i] = {o, v}; } sort(cc.begin(), cc.end()); cc.erase(unique(cc.begin(), cc.end()), cc.end()); for (int i = 0; i < Q; i++) if (Qs[i].first == 1) Qs[i].second = distance(cc.begin(), lower_bound(cc.begin(), cc.end(), Qs[i].second)); int sz = 0; for (int i = 0; i < Q; i++) { auto [o, v] = Qs[i]; if (o == 1) { sz++; fw.add(v, 1); } else { if (sz >= K) { int id = fw.select(K - 1); cout << cc[id] << endl; sz--; fw.add(id, -1); } else { cout << -1 << endl; } } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int tt = 1; // std::cin >> tt; while (tt--) { solve(); } }