#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 nbe[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 << as[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};
}
}
Node* merge(Node* a, Node* b) {
if(!a) return b;
if(!b) return a;
if(a->p < b->p) swap(a, b);
auto[l, r] = splitbyv(b, a->v);
a->l = merge(a->l, l);
a->r = merge(a->r, r);
pull(a);
return 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 as[a->b + s - size(a->l)];
}
}
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;});
// value -> index
vector<int> st;
for(int i = n-1; i >= 0; --i) {
while(!st.empty() && as[st.back()] < as[i]) {
st.pop_back();
}
if(st.empty()) nbe[i] = n;
else nbe[i] = st.back();
st.push_back(i);
}
int i = 0;
int t = 0;
Node* tr = nullptr;
for(int i = 0; i < n; i = nbe[i]) {
tr = concat(tr, new Node{i, nbe[i], as[i]});
}
D(tr)
bool changed = true;
for(int i = 0; i < q; ++i) {
while(t < qs[i].t && changed) {
auto[l, m, r] = splitons(tr, n/2);
D(l)
D(m)
D(r)
if(m == nullptr) {
changed = false;
tr = concat(l, r);
break;
}
pull(m);
Node* mrg = nullptr;
for(int i = m->b + n/2 - size(l); i < m->e; i = nbe[i]) {
mrg = concat(mrg, new Node{i, nbe[i], as[i]});
}
m->e = m->b + n/2 - size(l);
pull(m);
l = merge(l, mrg);
tr = concat(l, concat(m, r));
D(tr)
assert(size(tr) == n);
++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();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:193:9: warning: unused variable 'i' [-Wunused-variable]
193 | int i = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
37624 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
199 ms |
54480 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
11764 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
37624 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
