Submission #1305208
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
struct Node {
int val;
Node *lch, *rch;
int sz;
Node(int a) :val(a), lch(0), rch(0), sz(1) { init(); }
void init() { }
void push() { }
void update() { }
};
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;
struct RBST {
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(int x) { return lower_bound(root, x); }
int lower_bound(Node *t, int 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 change(int i, Node* v) { // i番目をvに更新
auto p = split(root, i);
auto a = p.first;
auto q = split(p.second, 1);
Node* b = q.first;
auto c = q.second;
b = v;
root = merge(merge(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 push_back(Node *t) {
root = merge(root, t);
}
void insert(int x) {
int k = lower_bound(x);
Node *a, *b;
tie(a, b) = split(root, k);
root = merge(a, new Node(x), b);
}
void erase(int 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);
}
Node* 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;
}
};
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
int Q;
RBST tree;
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> Q;
rep(q, 0, Q) {
int x, y; cin >> x >> y;
if (x == 1) {
tree.insert(y);
}
else {
int ans = tree.getAt(y - 1)->val;
printf("%d\n", ans);
tree.erase(ans);
}
}
}
Submission Info
Submission Time |
|
Task |
C - データ構造 |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4981 Byte |
Status |
AC |
Exec Time |
441 ms |
Memory |
9600 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
11 ms |
640 KB |
subtask1_05.txt |
AC |
28 ms |
1024 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
221 ms |
4736 KB |
subtask1_08.txt |
AC |
215 ms |
5632 KB |
subtask1_09.txt |
AC |
195 ms |
5632 KB |
subtask1_10.txt |
AC |
391 ms |
7680 KB |
subtask1_11.txt |
AC |
390 ms |
7552 KB |
subtask1_12.txt |
AC |
368 ms |
9600 KB |
subtask1_13.txt |
AC |
441 ms |
5632 KB |
subtask1_14.txt |
AC |
438 ms |
5632 KB |
subtask1_15.txt |
AC |
144 ms |
5632 KB |
subtask1_16.txt |
AC |
244 ms |
7680 KB |