結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2020-05-01 15:05:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 300 ms / 3,000 ms |
コード長 | 1,898 bytes |
コンパイル時間 | 2,161 ms |
コンパイル使用メモリ | 176,220 KB |
実行使用メモリ | 7,924 KB |
最終ジャッジ日時 | 2024-12-24 05:00:39 |
合計ジャッジ時間 | 8,741 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>#define REP(i, s, n) for (int i = s; i < n; i++)#define ALL(a) a.begin(), a.end()#define MOD 1000000007using namespace std;typedef long long ll;template <typename T>class BIT {public:BIT(int n) : N(n), A(n + 1, 0) {}T sum(int i) {T res = 0;while (i > 0) {res += A[i];i -= i & (-i);}return res;}T sum(int i, int j) {return sum(j) - sum(i - 1);}void add(int i, T x) {while (i <= N) {A[i] += x;i += (i & (-i));}}T lower_bound(int n) {if (n <= 0) return 0;T res = 0;int k = 1; while(k < N) k *= 2;for (int i = k / 2; i > 0; i /= 2) {if (res + i <= N && A[res + i] < n) {n -= A[res + i];res += i;}}return res + 1;}private:vector<T> A;int N;};int main() {int Q, K; cin >> Q >> K;vector<int> T(Q); vector<ll> V(Q), values;REP(i, 0, Q) {cin >> T[i];if (T[i] == 1) cin >> V[i], values.push_back(V[i]);}sort(ALL(values));values.erase(unique(ALL(values)), values.end());// for (auto v : values) cout << v << " ";// cout << endl;BIT<int> bit(values.size());REP(i, 0, Q) {// cout << "query : " << T[i] << endl;if (T[i] == 1) {int idx = lower_bound(ALL(values), V[i]) - values.begin();bit.add(idx + 1, 1);// cout << "--> add : " << V[i] << " at idx : " << idx + 1 << endl;;} else {if (K > bit.sum(values.size())) cout << -1 << endl;else {int idx = bit.lower_bound(K);cout << values[idx - 1] << endl;bit.add(idx, -1);}}}return 0;}