This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
const int TREE_SIZE=1<<18;
int n;
int l[200001];
int r[200001];
int tree[2*TREE_SIZE];
vector<int>init;
void update(int i,int val){
i+=TREE_SIZE;
tree[i]=val;
i/=2;
while(i){
tree[i]=tree[2*i]+tree[2*i+1];
i/=2;
}
}
pair<int,int>get(int node,int rl,int rr,int sum){
if(tree[node]<=sum)
return{rr,tree[node]};
if(rl==rr-1)
return{rl,0};
int mid=(rl+rr)/2;
if(sum<tree[2*node])
return get(2*node,rl,mid,sum);
else{
auto res=get(2*node+1,mid,rr,sum-tree[2*node]);
res.second+=tree[2*node];
return res;
}
}
void insert(int a,int b){
l[init[a]]=a;
r[init[a]]=b;
update(init[a],b-a);
}
pair<int,int>get(int sum){
auto res=get(1,0,TREE_SIZE,sum);
return{res.first,sum-res.second};
}
void solve(){
int q;
cin>>n>>q;
init.resize(n);
vector<int>nxt(n);
for(int&i:init)
cin>>i;
stack<pair<int,int>>st;
st.push({n+1,n});
for(int i=n-1;i>=0;i--){
while(st.top().first<init[i])
st.pop();
nxt[i]=st.top().second;
st.push({init[i],i});
}
vector<vector<pair<int,int>>>qrs(n+1);
vector<int>ans(q,-1);
for(int i=0;i<q;i++){
int t,qi;
cin>>t>>qi;
t=min(t,n);
qrs[t].push_back({qi-1,i});
}
for(int curr=0;curr<n;){
insert(curr,nxt[curr]);
curr=nxt[curr];
}
for(int round=0;round<=n;round++){
for(auto i:qrs[round]){
auto res=get(i.first);
ans[i.second]=init[l[res.first]+res.second];
}
auto res=get(n/2);
if(res.second==0)
continue;
int nl=l[res.first]+res.second;
int nr=r[res.first];
insert(l[res.first],nl);
for(int curr=nl;curr<nr;){
int nx=min(nxt[curr],nr);
insert(curr,nx);
curr=nx;
}
}
for(int i:ans){
if(i==-1)
abort();
cout<<i<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("input.in","r",stdin);freopen("output.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
/*
6 3
1 5 6 2 3 4
1 2
0 4
1 5
2
2
5
6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6
2
2
5
4
3
3
10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
2
3
6
1
7
5
8
4
9
10
10 10
5 4 3 10 9 8 7 6 2 1
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
1
2
5
4
3
6
8
7
10
9
*/
# | 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... |