結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
|
提出日時 | 2018-02-09 22:42:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 263 ms / 3,000 ms |
コード長 | 2,323 bytes |
コンパイル時間 | 1,696 ms |
コンパイル使用メモリ | 176,972 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2024-10-08 16:32:44 |
合計ジャッジ時間 | 5,110 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#define _USE_MATH_DEFINES#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define MT make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define RT return#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))using ll = long long;using pii = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;template<class Val>struct BinaryIndexedTree {int n;vector<Val> t;BinaryIndexedTree() {}BinaryIndexedTree(int _n) :n(_n + 1), t(_n + 1) {}void add(int k, Val val) {k++;while (k < n) {t[k] += val;k += (k&-k);}}void set(int k, Val val) {add(k, -sum(k, k + 1));add(k, val);}Val sum(int k) {Val r = 0;while (k > 0) {r += t[k];k -= (k&-k);}return r;}Val sum(int l, int r) {return sum(r) - sum(l);}};typedef BinaryIndexedTree<int> BIT;template<class Val>vector<Val> compress(vector<Val> &v) {vector<Val> a = v;sort(all(a));a.erase(unique(all(a)), a.end());each(b, v)b = (int)(lower_bound(all(a), b) - a.begin());return a;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(20);int Q, K;cin >> Q >> K;vll q(Q), v(Q, -1);rep(i, Q) {cin >> q[i];if (q[i] == 1)cin >> v[i];}auto c = compress(v);int N = sz(c);BIT bit(N);rep(i, Q) {if (q[i]==1) {bit.add((int)v[i], 1);} else {if (bit.sum(N) < K) {cout << -1 << endl;} else {int l = 0, r = N;while (r - l > 1) {int m = (l + r) >> 1;(bit.sum(m) >= K ? r : l) = m;}cout << c[r - 1] << endl;bit.add(r - 1, -1);}}}}