This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* In the name of God, aka Allah */
// Believe me - Takeshi Abo
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 2e5 + 50, LG = 20;
int n, q, par[N], out[N];
bool mark[N];
vector<pii> vc[N];
int p[N], pp[N];
int fen[N];
void upd(int i, int x) {
for (; i <= n; i += i&-i) fen[i] += x;
}
int get(int i) {
int out = 0;
for (; i > 0; i -= i&-i) out += fen[i];
return out;
}
int getpos(int x) {
int pos = 0;
for (int k = LG-1; k >= 0; k--) {
if (pos+(1<<k) <= n && fen[pos+(1<<k)] < x) {
pos ^= 1<<k;
x -= fen[pos];
}
}
return pos+1;
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> p[i];
pp[p[i]] = i;
}
for (int i = 1; i <= q; i++) {
int t, k;
cin >> t >> k;
t = min(t, n);
vc[t].push_back({k, i});
}
for (pii x:vc[0]) out[x.S] = p[x.F];
for (int i = n; i >= 1; i--) {
par[i] = i+1;
while (par[i] <= n && p[i] > p[par[i]]) {
par[i] = par[par[i]];
}
}
int pt = 1;
mark[n+1] = 1;
while (pt <= n/2 && !mark[pt]) {
mark[pt] = 1;
upd(p[pt], min(n/2+1, par[pt])-pt);
pt = par[pt];
}
pt = n/2+1;
while (!mark[pt]) {
mark[pt] = 1;
upd(p[pt], par[pt]-pt);
pt = par[pt];
}
for (int tt = 1; tt <= n; tt++) {
for (pii x:vc[tt]) {
int id = getpos(x.F);
out[x.S] = p[x.F-get(id-1)+pp[id]-1];
}
int id = getpos(n/2);
if (get(id) <= n/2) continue;
int pt = n/2-get(id-1)+pp[id];
upd(id, n/2-get(id));
while (!mark[pt]) {
mark[pt] = 1;
upd(p[pt], par[pt]-pt);
pt = par[pt];
}
}
for (int i = 1; i <= q; i++) {
cout << out[i] << endl;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |