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;
struct Query{
int t,i,ord;
};
void solve(){
int n,q;
cin>>n>>q;
vector<int>init(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<Query>>qrs(n+1);
vector<int>ans(q);
for(int i=0;i<q;i++){
Query nq;
nq.ord=i;
cin>>nq.t>>nq.i;
nq.t=min(nq.t,n);
nq.i--;
qrs[nq.t].push_back(nq);
}
set<pair<int,pair<int,int>>>s;
int sl=n;
vector<int>end(n,-1);
int end_end=n;
for(int curr=0;curr<n;){
s.insert({init[curr],{curr,nxt[curr]}});
curr=nxt[curr];
}
for(int round=0;round<=n;round++){
while(sl-((--s.end())->second.second-(--s.end())->second.first)>=n/2){
int last_len=(--s.end())->second.second-(--s.end())->second.first;
sl-=last_len;
end_end-=last_len;
for(int i=0;i<last_len;i++)
end[end_end+i]=init[(--s.end())->second.first+i];
s.erase(--s.end());
}
if(qrs[round].size()){
vector<int>vec=end;
int ci=0;
for(auto i:s){
for(int j=i.second.first;j<i.second.second;j++){
vec[ci++]=init[j];
}
}
for(auto i:qrs[round]){
ans[i.ord]=vec[i.i];
}
}
if(sl==n/2)
continue;
auto curr=(--s.end())->second;
s.erase(--s.end());
sl-=curr.second-curr.first;
auto nw=curr;
nw.second=nw.first+n/2-sl;
s.insert({init[nw.first],nw});
sl+=nw.second-nw.first;
curr.first=nw.second;
int prev=curr.first;
for(int i=curr.first+1;i<curr.second;i++){
if(init[i]>init[prev]){
s.insert({init[prev],{prev,i}});
sl+=i-prev;
prev=i;
}
}
s.insert({init[prev],{prev,curr.second}});
sl+=curr.second-prev;
}
for(int i:ans){
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
*/
# | 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... |