#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct nod {
int sz, pmax, vmax, val;
nod *l, *r;
} *nil = new nod{0, -1, -1, -1, 0, 0};
using ns = nod*;
vector<ns> ToDel;
ns nod_nou(int v) {
ns re = new nod{1, 0, v, v, nil, nil};
ToDel.push_back(re);
return re;
}
ns mod_fiu(ns a, int side, ns f) {
(side ? a->r : a->l) = f;
a->sz = a->l->sz + a->r->sz + 1;
int vl = a->l->vmax, eu = a->val, vr = a->r->vmax;
if(vl > eu && vl > vr) {
a->pmax = a->l->pmax;
a->vmax = vl;
}
if(eu > vl && eu > vr) {
a->pmax = a->l->sz;
a->vmax = eu;
}
if(vr > vl && vr > eu) {
a->pmax = a->r->pmax + a->l->sz + 1;
a->vmax = vr;
}
return a;
}
mt19937 rng(1);
ns join(ns a, ns b) {
return a == nil ? b :
b == nil ? a :
uniform_int_distribution<int>(1, a->sz + b->sz)(rng) <= a->sz ?
mod_fiu(a, 1, join(a->r, b)) /// a este tata
: mod_fiu(b, 0, join(a, b->l));
}
struct pns {
ns l, r;
};
pns split(ns a, int cnt) {
if(cnt > a->sz) {
cout << "Split prost\n";
exit(0);
}
if(a == nil)
assert(!a->sz);
pns tmp;
return !cnt ? pns{nil, a} :
cnt == a->sz ? pns{a, nil} :
a->l->sz >= cnt ?
(tmp = split(a->l, cnt), tmp.r = mod_fiu(a, 0, tmp.r), tmp)
: (tmp = split(a->r, cnt - a->l->sz - 1), tmp.l = mod_fiu(a, 1, tmp.l), tmp);
}
void afis(ns a) {
if(a == nil) return;
afis(a->l);
cout << a->val + 1 << " ";
afis(a->r);
}
vector<ns> Sparge(ns a) {
vector<ns> Re;
while(a->pmax) {
pns doi = split(a, a->pmax);
Re.push_back(doi.r);
a = doi.l;
}
Re.push_back(a);
return Re;
}
struct AIB {
int n;
vi V;
AIB(int N) : n(N + 1), V(N + 1, 0) {}
void update(int p, int v) {
++p;
while(p < n) {
V[p] += v;
p += p & -p;
}
}
int cauta(int v) {
///vreau prima pozitie pt care query(p) >= v
int p = 0;
for(int step = 20; step >= 0; --step)
if(p + (1 << step) < n && v >= V[p + (1 << step)]) {
p += (1 << step);
v -= V[p];
}
return p;
}
int query(int p) {
++p;
int re = 0;
while(p) {
re += V[p];
p -= p & -p;
}
return re;
}
};
int main() {
int n, q;
cin >> n >> q;
vi V0(n, 0);
ns A = nil, B = nil;
for(int i = 0; i < n; ++i) {
cin >> V0[i];
--V0[i];
if(i < n / 2) A = join(A, nod_nou(V0[i]));
else B = join(B, nod_nou(V0[i]));
}
AIB Sume(n);
auto SA = Sparge(A), SB = Sparge(B);
vector<ns> V(n, nil);
vi Sz(n, 0);
auto update = [&](ns nod, int sgn) {
if(nod == nil) return;
Sz[nod->vmax] += sgn * nod->sz;
V[nod->vmax] = nod;
Sume.update(nod->vmax, sgn * nod->sz);
};
vector<vector<ii> > Q(n);
vi Re(q, 0);
for(int i = 0; i < q; ++i) {
int t, p;
cin >> t >> p;
Q[min(t, n / 2)].push_back({i, p});
}
for(auto [id, p] : Q[0]) Re[id] = V0[p - 1];
for(auto it : SA)
update(it, 1);
for(auto it : SB)
update(it, 1);
for(int t = 1; t <= n / 2; ++t) {
for(auto [id, p] : Q[t]) {
int p1 = Sume.cauta(p - 1);
ns eu = V[p1];
int nr = p - Sume.query(p1 - 1) - 1;
pns a = split(eu, nr);
pns b = split(a.r, 1);
Re[id] = b.l->val;
eu = join(a.l, join(b.l, b.r));
V[p1] = eu;
}
int p = Sume.cauta(n / 2);
if(Sume.query(p) == n / 2) { /// nu trebuie facut nimic
continue;
}
update(V[p], -1);
pns nou = split(V[p], n / 2 - Sume.query(p - 1));
update(nou.l, 1);
update(nou.r, 1);
}
for(auto it : Re)
cout << it + 1 << "\n";
for(auto it : ToDel)
delete it;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
764 ms |
25276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1233 ms |
52872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
14304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
764 ms |
25276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
