#include <bits/stdc++.h>
using namespace std;
using un = long long;
using vuc = vector<un>;
using vol = vector<bool>;
#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
un N;
vuc zac;
vuc A;
vuc vel_iv;
un M;
void init_iv(){
M = N;
while(M&(M-1)) M++;
vel_iv = vuc(2*M);
}
un get_iv(un i) {return vel_iv[M+i];}
void set_iv(un i, un v){
i += M;
vel_iv[i] = v;
i/= 2;
while(i > 0) {
vel_iv[i] = vel_iv[2*i] + vel_iv[2*i + 1];
i /= 2;
}
}
pair<un, un> dostat_pozicy(un i){
i++;
un ptr = 1;
while(ptr < M){
if (i <= vel_iv[2*ptr]) {
ptr = 2*ptr;
}
else{
i -= vel_iv[2*ptr];
ptr = 2*ptr + 1;
}
}
return {ptr-M, i-1};
}
unordered_map<un, un> cache;
un dostat(un i){
if (cache.find(i) == cache.end()){
auto [a, b] = dostat_pozicy(i);
cache[i] = A[zac[a] + b];
}
return cache[i];
}
bool doStep(){
auto [a, b] = dostat_pozicy(N/2);
if (b == 0) return true;
un nej = -1;
un val = 0;
REP(i, zac[a]+b, zac[a]+get_iv(a)){
if (A[i] > nej){
if (nej != -1) set_iv(nej, val);
nej = A[i];
val = 0;
}
val++;
}
set_iv(nej, val);
set_iv(a, b);
return false;
}
int main(){
un Q; cin >> N >> Q;
init_iv();
A = vuc(N); FEAC(a, A) cin >> a;
FEAC(a, A) a--;
zac = vuc(N, -1);
vec<tuple<un, un, un>> queries;
REP(i, 0, Q){
un a, b; cin >> a >> b;
b--;
queries.emplace_back(a, b, i);
}
sort(ALL(queries));
un val = 0;
un nej = -1;
REP(i, 0, N){
zac[A[i]] = i;
if (A[i] > nej){
if(nej != -1) set_iv(nej, val);
nej = A[i];
val = 0;
}
val++;
}
set_iv(nej, val);
vuc rets(Q, -1);
un qIndex = 0;
un t = 0;
while(qIndex < Q){
while((qIndex < Q) and (get<0>(queries[qIndex]) == t)){
auto [ignore, i, j] = queries[qIndex];
rets[j] = dostat(i);
qIndex++;
}
bool hotovo = doStep();
t++;
cache = unordered_map<un, un>();
if (hotovo) break;
}
while(qIndex < Q){
auto [ignore, i, j] = queries[qIndex];
rets[j] = dostat(i);
qIndex++;
}
FEAC(ret, rets) cout << ret+1 << endl;
}
# | 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... |