#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];
struct Node {
int v;
int s = 1;
int p = rand();
Node* l = nullptr;
Node* r = nullptr;
Node* c = 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 << "| ";
if(pos == 2) o << "c ";
o << ",-o\n";
} else {
if(pos == -1) l->print(o, bef + " ", -1);
if(pos == 1) l->print(o, bef + "| ", -1);
if(pos == 2) l->print(o, bef + "c ", -1);
if(pos == 0) l->print(o, bef, -1);
}
o << bef;
if(pos == -1) o << ",-";
if(pos == 1) o << "`-";
if(pos == 2) o << "c-";
o << "(v: " << v << ", p: " << p << ", s:" << s << ")\n";
if(c) {
if(pos == -1) c->print(o, bef + "| | ", 2);
if(pos == 1) c->print(o, bef + " | ", 2);
if(pos == 2) c->print(o, bef + " | ", 2);
if(pos == 0) c->print(o, bef + "| ", 2);
}
if(r == nullptr) {
o << bef;
if(pos == -1) o << "| ";
if(pos == 1) o << " ";
if(pos == 2) o << " ";
o << "`-o\n";
} else {
if(pos == -1) r->print(o, bef + "| ", 1);
if(pos == 1) r->print(o, bef + " ", 1);
if(pos == 2) 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;
}
};
Node buf[200000];
int size(Node* a) {
return a?a->s:0;
}
void pull(Node* a) {
if(a) {
a->s = 1;
a->s += size(a->l);
a->s += size(a->r);
a->s += size(a->c);
}
}
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};
}
}
Node* merge2(Node* a, Node* b) {
if(!a) return b;
if(!b) return a;
if(b->p > a->p) swap(a, b);
auto [l, r] = splitbyv(b, a->v);
a->l = merge2(l, a->l);
a->r = merge2(r, a->r);
pull(a);
return a;
}
Node* merge(Node* a, Node* b) {
if(!a) return b;
if(!b) return a;
if(a->s > b->s) swap(a, b);
b = merge(a->l, b);
a->l = nullptr;
b = merge(a->r, b);
a->r = nullptr;
pull(a);
auto [l, r] = splitbyv(b, a->v);
b = concat(l, concat(a, r));
return b;
}
struct SplitRes {
Node* l;
Node* m;
Node* r;
};
SplitRes splitons(Node* a, int s) {
D(s)
D(a)
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) + size(a->c) + 1) {
auto[l, m, r] = splitons(a->r, s - size(a->c) - size(a->l) - 1 );
a->r = l;
pull(a);
return {a, m, r};
} else {
auto[l, m, r] = splitons(a->c, s - size(a->l) - 1);
m = concat(m, r);
a->c = l;
auto ar = a->r;
a->r = nullptr;
pull(a);
return {a, m, ar};
}
}
int valuebys(Node* a, int s) {
D(size(a))
if(s < size(a->l)) {
return valuebys(a->l, s);
} else if(s == size(a->l)) {
return a->v;
} else if(s < size(a->l) + 1 + size(a->c)) {
return valuebys(a->c, s - size(a->l) - 1);
} else {
return valuebys(a->r, s - size(a->l) - 1 - size(a->c));
}
}
struct Q {
int t;
int ind;
int i;
int res;
};
void solve() {
int n, q;
cin >> n >> q;
srand(4994040);
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;});
vector<Node*> trs;
for(int i = n-1; i >= 0; --i) {
Node* tr = buf+i;
tr->v = as[i];
tr->s = 1;
tr->p = rand();
while(!trs.empty() && trs.back()->v < tr->v) {
tr->c = concat(tr->c, trs.back());
trs.pop_back();
}
pull(tr);
trs.push_back(tr);
}
Node* tr = nullptr;
for(Node* t : trs) {
tr = concat(t, tr);
}
trs.clear();
D(tr);
D(size(tr));
int t = 0;
bool changed = true;
for(int i = 0; i < q; ++i) {
D(i)
while(changed && qs[i].t > t && t < 10) {
D(t)
auto [l, m, r] = splitons(tr, n/2);
if(m == nullptr) changed = false;
D(l)
D(m)
D(r)
l = merge(l, m);
D(l)
tr = concat(l, r);
D(tr)
++t;
}
D(t)
qs[i].res = valuebys(tr, qs[i].ind);
}
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 |
Incorrect |
766 ms |
35316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3050 ms |
34628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
11732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
766 ms |
35316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
