結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2018-02-10 01:06:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 330 ms / 3,000 ms |
コード長 | 5,046 bytes |
コンパイル時間 | 2,295 ms |
コンパイル使用メモリ | 189,368 KB |
実行使用メモリ | 13,184 KB |
最終ジャッジ日時 | 2024-10-09 09:13:56 |
合計ジャッジ時間 | 7,973 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h>#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,a,b) for(int i=a;i>=b;i--)#define fore(i,a) for(auto &i:a)#define all(x) (x).begin(),(x).end()#pragma GCC optimize ("-O3")using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }//---------------------------------------------------------------------------------------------------struct dice {mt19937 mt; dice() { random_device rd; mt = mt19937(rd()); }int operator()(int x) { return this->operator()(0, x - 1); }int operator()(int x, int y) { uniform_int_distribution<int> dist(x, y); return dist(mt); }} dc;using V = ll;struct RBST {struct Node {V val;Node *lch, *rch;int sz;Node(V a) :val(a), lch(0), rch(0), sz(1) { init(); }void init() { }void push() { }void update() { }};RBST() :root(NULL) {}Node *root;inline int getsz(Node *t) { return t ? t->sz : 0; }int getsz() { return getsz(root); }inline void push(Node *t) {if (t == NULL)return;t->push();}inline Node *update(Node *t) {if (!t)return NULL;t->sz = getsz(t->lch) + getsz(t->rch) + 1;t->update();return t;}Node *merge(Node *a, Node *b) {push(a); push(b);if (!a)return b;if (!b)return a;if (dc(getsz(a) + getsz(b))<getsz(a)) {a->rch = merge(a->rch, b);return update(a);}else {b->lch = merge(a, b->lch);return update(b);}}template<class... T> Node *merge(Node *a, T... y) { return merge(a, merge(y...)); }pair<Node *, Node *>split(Node *t, int k) {//[0,k) [k,N)push(t);if (!t)return make_pair(t, t);if (k <= getsz(t->lch)) {pair<Node *, Node *>s = split(t->lch, k);t->lch = s.second;return make_pair(s.first, update(t));}else {pair<Node *, Node *>s = split(t->rch, k - getsz(t->lch) - 1);t->rch = s.first;return make_pair(update(t), s.second);}}int lower_bound(V x) { return lower_bound(root, x); }int lower_bound(Node *t, V x) {push(t);if (!t)return 0;if (t->val >= x)return lower_bound(t->lch, x);return lower_bound(t->rch, x) + getsz(t->lch) + 1;}// [l,r]番目でa,b,cに分ける(終わったらちゃんとマージすること)// rootは0になってるtuple<Node*, Node*, Node*> split3(int l, int r) {auto p = split(root, l);auto a = p.first;auto q = split(p.second, r - l + 1);auto b = q.first;auto c = q.second;root = 0;return make_tuple(a, b, c);}void dump() {dump(root);cout << endl;}void dump(Node *t) {if (t == NULL)return;push(t);dump(t->lch);cout << t->val << " ";dump(t->rch);}void insert(V x) {int k = lower_bound(x);Node *a, *b;tie(a, b) = split(root, k);root = merge(a, new Node(x), b);}void erase(V x) {int k = lower_bound(x);Node *a, *b;tie(a, b) = split(root, k);Node *ba, *bb;tie(ba, bb) = split(b, 1);root = merge(a, bb);}V getAt(int i) {auto p = split(root, i);auto a = p.first;auto q = split(p.second, 1);Node* b = q.first;auto c = q.second;root = merge(merge(a, b), c);return b->val;}};/*---------------------------------------------------------------------------------------------------∧_∧∧_∧ (´<_` ) Welcome to My Coding Space!( ´_ゝ`) / ⌒i/ \ | |/ / ̄ ̄ ̄ ̄/ |__(__ニつ/ _/ .| .|____\/____/ (u ⊃---------------------------------------------------------------------------------------------------*/int Q, K;RBST rbst;//---------------------------------------------------------------------------------------------------void _main() {cin >> Q >> K;rep(q, 0, Q) {int t; cin >> t;if (t == 1) {ll v; cin >> v;rbst.insert(v);}else {int n = rbst.getsz();if (n < K) printf("-1\n");else {ll ans = rbst.getAt(K - 1);rbst.erase(ans);printf("%lld\n", ans);}}}}