#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ceoi=b;i<ceoi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto kdjfhg:v)cout<<kdjfhg<<" ";cout<<"\n"
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e6+5;
vector<ll> f(vector<ll>a){
vector<ll>l,r;
ll n=SZ(a);
fore(i,0,n/2)l.pb(a[i]);
fore(i,n/2,n)r.pb(a[i]);
vector<ll>b;
reverse(ALL(l)); reverse(ALL(r));
while(SZ(l)+SZ(r)){
if(!SZ(r)||(SZ(l)&&l.back()<r.back()))b.pb(l.back()),l.pop_back();
else b.pb(r.back()),r.pop_back();
}
return b;
}
ll ft[MAXN],arr[MAXN];
ll n;
void upd(ll i, ll v){
//cout<<"new "<<i<<" "<<v<<"\n";
arr[i]+=v;
for(i++;i<=MAXN;i+=i&-i)ft[i]+=v;
}
ll get_sum(ll i){ // )
ll res=0;
for(;i;i-=i&-i)res+=ft[i];
return res;
}
ii find(ll x){ //upperbound on prefix sums, (pos,remainder)
ll l=0,r=n-1;
while(l<=r){
ll m=(l+r)/2;
if(get_sum(m+1)>x)r=m-1;
else l=m+1;
}
r=x-get_sum(l);
//cout<<"find "<<x<<": "<<l<<","<<r<<endl;
//fore(i,0,n)cout<<arr[i]<<" ";;cout<<endl;
return {l,r};
}
int main(){
ll q; cin>>n>>q;
vector<ll>a(n),p(n);
fore(i,0,n)cin>>a[i],a[i]--,p[a[i]]=i;
vector<vector<ii>>qs(n+5);
vector<ll>ans(q);
fore(_,0,q){
ll t,i; cin>>t>>i; i--;
t=min(t,n+3);
qs[t].pb({i,_});
}
vector<ll>nx(n);
for(ll i=n-1;i>=0;i--)
for(nx[i]=i+1;nx[i]!=n&&a[i]>=a[nx[i]];nx[i]=nx[nx[i]]);
ll mx=0;
fore(i,0,n){
mx=max(mx,a[i]);
if(a[i]==mx)upd(a[i],nx[i]-i);
}
//fore(i,0,n)cout<<nx[i]<<" ";;cout<<"\n";
fore(t,0,n+5){
//cout<<"time "<<t<<endl;
for(auto [i,_]:qs[t]){
auto [x,r]=find(i);
ans[_]=a[p[x]+r];
}
auto [x,r]=find(n/2);
if(r==0)continue; //x==i
upd(x,-arr[x]+r);
//cout<<nx[p[x]]<<")\n";
for(ll i=p[x]+r;i<nx[p[x]];i=nx[i])upd(a[i],nx[i]-i);
//for(ll i=a[p[x]+r];i<nx[p[x]];i=a[nx[p[i]])upd(i,nx[p[i]]-p[i]);
}
fore(_,0,q)cout<<ans[_]+1<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
425 ms |
45516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
645 ms |
59308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
19024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
425 ms |
45516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
