#include<bits/stdc++.h>
using namespace std;
int N, Q;
int cur;
vector<int> A, nxtg, subans;
vector<pair<int, int>> q;
set<array<int, 3>> S;// original segment {L, R};
void shuffle_go() {
if(cur == N / 2) {
return;
}
auto x = end(S); --x;
while(x != begin(S) && cur - ((*x)[2] - (*x)[1] + 1) >= N / 2) {
cur -= ((*x)[2] - (*x)[1] + 1);
for(int i = (*x)[2]; i >= (*x)[1]; --i) {
subans.push_back(A[i]);
}
x = S.erase(x); --x;
}
if(cur == N / 2) {
return;
}
array<int, 3> mv = *x;
S.erase(x);
int trsh = cur - N / 2;
S.insert({mv[0], mv[1], mv[2] - trsh});
int L = mv[2] - trsh + 1;
int R = mv[2];
for(int i = L; i <= R; ++i) {
int j = min(R, nxtg[i] - 1);
S.insert({A[i], i, j});
i = j;
}
}
int32_t main() {
cin >> N >> Q;
cur = N;
A.resize(N); for(int& u : A) cin >> u;
q.resize(Q); for(auto& u : q) { cin >> u.first >> u.second; }
{
nxtg.resize(N, N);
vector<int> st;
for(int i = N - 1; i >= 0; --i) {
while(!st.empty() && A[st.back()] < A[i]) st.pop_back();
if(!st.empty()) nxtg[i] = st.back();
st.push_back(i);
}
}
if(q[0].first == 0) {
for(auto& u : q) {
cout << A[u.second - 1] << '\n';
}
return 0;
}
//first change manually
for(int i = 0; i < N / 2; ++i) {
int j = min(nxtg[i] - 1, N / 2 - 1);
S.insert({A[i], i, j});
i = j;
}
for(int i = N / 2; i < N; ++i) {
int j = nxtg[i] - 1;
S.insert({A[i], i, j});
i = j;
}
for(int i = 1; i < q[0].first; ++i) {
shuffle_go();
}
vector<int> wtf;
for(auto& u : S) {
// cout << u[0] << '\n';
for(int i = u[1]; i <= u[2]; ++i) {
wtf.push_back(A[i]);
}
}
reverse(begin(subans), end(subans));
for(auto& u : subans) {
// cout << u << '\n';
wtf.push_back(u);
}
for(auto& u : q) {
// cout << u << ' ';
cout << wtf[u.second - 1] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
