#include <bits/stdc++.h>
#ifdef GUDEB
#define D(x) cerr << #x << ": " << (x) << '\n';
#define ifdeb if(true)
#else
#define D(x) ;
#define ifdeb if(false)
#endif
#define all(x) begin(x), end(x)
using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;
int as[200000];
int nas[200000];
struct Node {
int b;
int e;
int v;
int s = e - b;
int p = rand();
Node* l = nullptr;
Node* r = nullptr;
void print(ostream& o, string bef = string{}, int pos = 0) const {
if(l == nullptr) {
o << bef;
if(pos == -1) o << " ";
if(pos == 1) o << "| ";
o << ",-o\n";
} else {
if(pos == -1) l->print(o, bef + " ", -1);
if(pos == 1) l->print(o, bef + "| ", -1);
if(pos == 0) l->print(o, bef, -1);
}
o << bef;
if(pos == -1) o << ",-";
if(pos == 1) o << "`-";
o << "(v: " << v << ", p: " << p << ", s:" << s << ", b: " << b << ", e: " << e << ")\n";
o << bef;
if(pos == -1) o << "| | ";
if(pos == 1) o << " | ";
for(int i = b; i < e; ++i) o << nas[i] << ' ';
o << '\n';
if(r == nullptr) {
o << bef;
if(pos == -1) o << "| ";
if(pos == 1) o << " ";
o << "`-o\n";
} else {
if(pos == -1) r->print(o, bef + "| ", 1);
if(pos == 1) r->print(o, bef + " ", 1);
if(pos == 0) r->print(o, bef, 1);
}
}
friend ostream& operator<< (ostream& o, const Node* a) {
o << '\n';
if(!a) o << "o\n";
else a->print(o);
return o;
}
};
int size(Node* a) {
return a?a->s:0;
}
void pull(Node* a) {
if(a) {
a->s = a->e - a->b;
a->s += size(a->r);
a->s += size(a->l);
}
}
Node* concat(Node* a, Node* b) {
if(!a) return b;
if(!b) return a;
if(a->p > b->p) {
a->r = concat(a->r, b);
pull(a);
return a;
} else {
b->l = concat(a, b->l);
pull(b);
return b;
}
}
pair<Node*, Node*> splitbyv(Node* a, int v) {
if(!a) return {a, a};
if(a->v < v) {
auto [rl, rr] = splitbyv(a->r, v);
a->r = rl;
pull(a);
return {a, rr};
} else {
auto [ll, lr] = splitbyv(a->l, v);
a->l = lr;
pull(a);
return {ll, a};
}
}
array<Node*, 3> splitons(Node* a, int s) {
if(!a) return {a, a, a};
if( s <= size(a->l) ) {
auto[l, m, r] = splitons(a->l, s);
a->l = r;
pull(a);
return {l, m, a};
} else if(s >= size(a->l) + a->e - a->b ) {
auto[l, m, r] = splitons(a->r, s - size(a->l) - a->e + a->b);
a->r = l;
pull(a);
return {a, m, r};
} else {
Node* l = a->l;
Node* r = a->r;
a->l = nullptr;
a->r = nullptr;
pull(a);
return {l, a, r};
}
}
int valuebys(Node* a, int s) {
D(size(a))
if(s < size(a->l)) {
return valuebys(a->l, s);
} else if( size(a->l) + a->e - a->b <= s) {
return valuebys(a->r, s - size(a->l) - a->e + a->b);
} else {
return nas[a->b + s - size(a->l)];
}
}
Node* first(Node* a) {
if(!a) return a;
if(a->l) return first(a->l);
return a;
}
Node* last(Node* a) {
if(!a) return a;
if(a->r) return last(a->r);
return a;
}
struct Q {
int t;
int ind;
int i;
int res;
};
void solve() {
int n, q;
cin >> n >> q;
vector<Q> qs(q);
for(int i = 0; i < n; ++i) {
cin >> as[i];
}
for(int i = 0; i < q; ++i) {
cin >> qs[i].t >> qs[i].ind;
--qs[i].ind;
qs[i].i = i;
}
sort(all(qs), [](Q a, Q b){return a.t < b.t;});
int i = 0;
int t = 0;
while(i < q && qs[i].t == 0) {
qs[i].res = as[qs[i].ind];
++i;
}
Node* tr = nullptr;
{
Node* tb = nullptr;
int o = 0;
int i1 = 0;
int i2 = n/2;
while(i1 < n/2 && i2 < n) {
if(as[i1] < as[i2]) {
nas[o] = as[i1];
++o;
++i1;
} else {
nas[o] = as[i2];
++o;
++i2;
}
}
while(i1 < n/2) {
nas[o] = as[i1];
++o;
++i1;
}
while(i2 < n) {
nas[o] = as[i2];
++o;
++i2;
}
tb = new Node{0, 1, nas[0]};
ifdeb {
for(int i = 0; i < n; ++i)
cerr << nas[i] << ' ';
cerr << '\n';
}
for(int j = 1; j < n; ++j) {
if(nas[j] <= nas[j-1]) {
++tb->e;
} else {
pull(tb);
D(size(tb))
tr = concat(tr, tb);
tb = new Node{j, j+1, nas[j]};
}
}
tr = concat(tr, tb);
}
++t;
bool changed = true;
while(i < q) {
D(i)
while(t < qs[i].t && changed) {
changed = false;
D(size(tr))
auto[l, m, r] = splitons(tr, n/2);
D(l);
D(r);
D(size(l))
D(size(m))
D(size(r))
if(m != nullptr) {
Node* ml = m;
Node* mr = new Node{n/2 - size(l) + m->b, m->e, nas[n/2 - size(l) + m->b]};
assert(ml != nullptr);
assert(mr != nullptr);
assert(size(ml) != 0);
assert(size(mr) != 0);
ml->e = n/2 - size(l) + m->b;
ml->s = m->e - m->b;
l = concat(l, ml);
r = concat(mr, r);
}
D(l);
D(r);
Node* fstr = first(r);
Node* lstl = last(l);
while(l && r && fstr->v < lstl->v) {
changed = true;
D(l)
D(r)
auto [af, b, nr] = splitons(r, fstr->e - fstr->b);
D(af)
D(b)
D(nr)
assert(!b);
auto [ll, lr] = splitbyv(l, af->v);
l = concat(ll, concat(af, lr));
r = nr;
fstr = first(r);
}
tr = concat(l, r);
assert(size(tr) == n);
++t;
D(t);
D(tr);
}
qs[i].res = valuebys(tr, qs[i].ind);
++i;
}
D(tr)
sort(all(qs), [](Q a, Q b){return a.i < b.i;});
for(auto q : qs) cout << q.res << '\n';
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << setprecision(20);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
323 ms |
19900 KB |
Output is correct |
| 2 |
Correct |
323 ms |
19868 KB |
Output is correct |
| 3 |
Correct |
306 ms |
19096 KB |
Output is correct |
| 4 |
Incorrect |
303 ms |
19000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
400 ms |
31224 KB |
Output is correct |
| 2 |
Correct |
363 ms |
32620 KB |
Output is correct |
| 3 |
Correct |
285 ms |
25928 KB |
Output is correct |
| 4 |
Incorrect |
259 ms |
23664 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
7868 KB |
Output is correct |
| 2 |
Correct |
85 ms |
7928 KB |
Output is correct |
| 3 |
Correct |
97 ms |
7628 KB |
Output is correct |
| 4 |
Incorrect |
59 ms |
5384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
323 ms |
19900 KB |
Output is correct |
| 2 |
Correct |
323 ms |
19868 KB |
Output is correct |
| 3 |
Correct |
306 ms |
19096 KB |
Output is correct |
| 4 |
Incorrect |
303 ms |
19000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
