#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define bc back()
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}*/
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=1e6+7;
ll ind[N],arr[N];
set<ll> st;
ll n,ans[N];
vector <ll> t(4*N);
void upd(ll v,ll tl,ll tr,ll pos,ll val){
if(tl>pos || tr<pos)return;
if(tl==tr && pos==tl){
t[v]=val;
return;
}
ll tm=(tl+tr)/2;
upd(v*2,tl,tm,pos,val);
upd(v*2+1,tm+1,tr,pos,val);
t[v]=t[v*2]+t[v*2+1];
}
bool shuffle(ll v,ll l,ll r,ll val){
if(l==r){
if(t[v]>val){
ll mx=-1,c=0;
for(ll i=ind[l]+val;i<t[v]+ind[l];i++){
if(arr[i]>mx || i==t[v]+ind[l]-1){
mx=arr[i];
upd(1,1,n,mx,c);
c=0;
}
c++;
}
upd(1,1,n,l,val);
return false;
}
else{
return true;
}
}
ll mid=(l+r)/2;
if(t[v*2]>=val){
shuffle(v*2,l,mid,val);
}
else{
shuffle(v*2+1,mid+1,r,val-t[v*2]);
}
}
ll go(ll v,ll l,ll r,ll val){
if(l==r){
if(t[v]>val){
return arr[ind[l]+val];
}
else{
return arr[ind[l]];
}
}
ll mid=(l+r)/2;
if(t[v*2]>=val){
go(v*2,l,mid,val);
}
else{
go(v*2+1,mid+1,r,val-t[v*2]);
}
}
void solve(){
ll i,j,q,sum=0,a=1,b,mx=-1,c=0,m;
deque <pair<pair<ll,ll>,ll>> v;
cin>>n>>q;
m=q;
for(i=1;i<=n;i++){
cin>>arr[i];
ind[arr[i]]=i;
if (i==n){
c++;
upd(1,1,n,mx,c);
}
else if(arr[i]>mx || i==n/2+1){
upd(1,1,n,mx,c);
mx=arr[i];
c=0;
}
c++;
}
c=1;
while(q--){
cin>>a>>b;
v.pb({{a,b},c});
c++;
}
sort(v.begin(),v.end());
bool flag=false;
c=1;
while(v.sz>0){
if(v[0].fr.fr==0){
ans[v[0].sc]=arr[v[0].fr.sc];
v.pop_front();
continue;
}
if(flag){
ans[v[0].sc]=go(1,1,n,v[0].fr.sc);
v.pop_front();
continue;
}
while(c<v[0].fr.fr){
if(shuffle(1,1,n,n/2)){
flag=true;
break;
}
c++;
}
ans[v[0].sc]=go(1,1,n,v[0].fr.sc);
v.pop_front();
}
for(i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
}
signed main(){
//start();
//fre("");
ll t=1;
//cin>>t;
while(t--) solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:85:10: warning: unused variable 'j' [-Wunused-variable]
85 | ll i,j,q,sum=0,a=1,b,mx=-1,c=0,m;
| ^
Main.cpp:85:14: warning: unused variable 'sum' [-Wunused-variable]
85 | ll i,j,q,sum=0,a=1,b,mx=-1,c=0,m;
| ^~~
Main.cpp: In function 'bool shuffle(long long int, long long int, long long int, long long int)':
Main.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
66 | }
| ^
Main.cpp: In function 'long long int go(long long int, long long int, long long int, long long int)':
Main.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
83 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
606 ms |
127020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
790 ms |
133836 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
73700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
606 ms |
127020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
