結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
 るこーそー
|
| 提出日時 | 2024-11-14 15:55:11 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,015 bytes |
| コンパイル時間 | 3,362 ms |
| コンパイル使用メモリ | 254,976 KB |
| 実行使用メモリ | 17,096 KB |
| 最終ジャッジ日時 | 2024-11-14 15:56:49 |
| 合計ジャッジ時間 | 98,031 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 9 TLE * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename S, S (*op)(S,S), S (*e)(), typename F, S (*mapping)(F,S), F (*composition)(F,F), F (*id)()>class SplayTree{private:struct node{S v, prod;F lazy;int cnt, rev;node *l, *r;node(S v): v(v), prod(v), lazy(id()), cnt(1), rev(0){l = r = nullptr;}};node *root=nullptr;int count(node *x){return !x ? 0:x->cnt;}S sum(node *x){return !x ? e():x->prod;}void push(node *x){if (!x)return;if (x->lazy!=id()){x->v=mapping(x->lazy,x->v);x->prod=mapping(x->lazy,x->prod);if (x->l)x->l->lazy=composition(x->lazy,x->l->lazy);if (x->r)x->r->lazy=composition(x->lazy,x->r->lazy);x->lazy=id();}if (x->rev){swap(x->l,x->r);if (x->l)x->l->rev^=1;if (x->r)x->r->rev^=1;x->rev=0;}}void all_push(node *x){push(x);if (x)push(x->l),push(x->r);}node *update(node *x){if (!x)return x;x->cnt=count(x->l)+count(x->r)+1;x->prod=op(op(sum(x->l),x->v),sum(x->r));return x;}node *rotate(node *x,bool right){node *y= right ? x->l : x->r;all_push(x);all_push(y);if (!y)return x;if (right){x->l=y->r;y->r=x;}else{x->r=y->l;y->l=x;}update(x);update(y);return y;}node *splay(node *x,int k){if (!x)return nullptr;all_push(x);if (k<count(x->l)){if (x->l==nullptr)return x;if (k<count(x->l->l)){x->l->l=splay(x->l->l,k);x=rotate(x,true);}else if (count(x->l->l)<k){x->l->r=splay(x->l->r,k-count(x->l->l)-1);if (x->l->r)x->l=rotate(x->l,false);}return x->l ? rotate(x,true) : update(x);}else if (count(x->l)<k){if (x->r==nullptr)return x;k=k-count(x->l)-1;if (k<count(x->r->l)){x->r->l=splay(x->r->l,k);if (x->r->l)x->r=rotate(x->r,true);}else if (count(x->r->l)<k){x->r->r=splay(x->r->r,k-count(x->r->l)-1);x=rotate(x,false);}return x->r ? rotate(x,false) : update(x);}return update(x);}node *merge(node *l,node *r) {if (!l || !r) return !l ? r : l;r=splay(r,0);r->l=l;return update(r);}pair<node*, node*> split(node *x, int k) {assert(0<=k && k<=size());if (!x) return {nullptr, nullptr};if (k==size())return {x,nullptr};x=splay(x, k);node* l=x->l;x->l=nullptr;return {l,x};}tuple<node*, node*, node*> split3(node *x,int l,int r){//[0,l),[l,r),[r,size)auto [left_mid,right]=split(x,r);auto [left,mid]=split(left_mid,l);return {left,mid,right};}int bisect_left(node *x,S v){all_push(x);if (!x)return 0;if (v<=x->v)return bisect_left(x->l,v);return count(x->l)+1+bisect_left(x->r,v);}int bisect_right(node *x,S v){all_push(x);if (!x)return 0;if (v<x->v)return bisect_right(x->l,v);return count(x->l)+1+bisect_right(x->r,v);}public:int size(){all_push(root);update(root);return (!root ? 0 : root->cnt);}void insert(int k,S v) {assert(0<=k && k<=size());auto [l,r]=split(root,k);root=merge(merge(l,new node(v)),r);}void erase(int k) {assert(0<=k && k<size());root=splay(root,k);auto [left_mid,right]=split(root,k+1);auto [left,mid]=split(left_mid,k);delete mid;root=merge(left,right);}SplayTree merge(SplayTree other){node *new_root=merge(root,other.root);SplayTree res;res.root=new_root;return res;}pair<SplayTree,SplayTree> split(int k){auto [left,right]=split(root,k);SplayTree l,r;all_push(left);all_push(right);update(left);update(right);l.root=left;r.root=right;return {l,r};}S get(int k){assert(0<=k && k<size());if (!root)return e();root=splay(root,k);all_push(root);update(root);return root->v;}void set(int k,S v){assert(0<=k && k<size());root=splay(root,k);root->v=v;}S prod(int l,int r) {assert(0<=l && r<=size() && l<=r);root=splay(root,l);auto [left,mid,right]=split3(root,l,r);all_push(mid);S res=sum(update(mid));root=merge(merge(left,mid),right);return res;}void apply(int l,int r,F f){assert(0<=l && r<=size() && l<=r);root=splay(root,l);auto [left,mid,right]=split3(root,l,r);if (mid)mid->lazy=composition(f,mid->lazy);root=merge(merge(left,mid),right);}void reverse(int l,int r){assert(0<=l && r<=size() && l<=r);root=splay(root,l);auto [left,mid,right]=split3(root,l,r);if (mid)mid->rev=1;root=merge(merge(left,mid),right);}void insert(int k,SplayTree other){assert(0<=k && k<=size());root=splay(root,k);all_push(root);auto [left,right]=split(root,k);root=merge(merge(left,other.root),right);}void erase(int l,int r){assert(0<=l && r<=size() && l<=r);root=splay(root,l);auto [left,mid,right]=split3(root,l,r);all_push(root);delete mid;root=merge(left,right);}int bisect_left(S v){root=splay(root,size());return bisect_left(root,v);}int bisect_right(S v){root=splay(root,size());return bisect_right(root,v);}void balance(){while (root && abs(count(root->l)-count(root->r))>100){if (count(root->l)>count(root->r)){root=rotate(root,true);}else{root=rotate(root,false);}}}};using S=long long;S op(S a,S b){return min(a,b);}S e(){return 0;}using F=long long;S mapping(F f,S x){return f+x;}F composition(F f,F g){return f+g;}F id(){return 0;}void solve() {SplayTree<S,op,e,F,mapping,composition,id> st;int q,k;cin >> q >> k;while (q--){long long t,x;cin >> t;if (t==1){cin >> x;st.insert(st.bisect_left(x),x);}else {if (k<=st.size()){cout << st.get(k-1) << endl;st.erase(k-1);}else{cout << -1 << endl;}}st.balance();}}int main() {solve();}