#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(int i=s;i<f;i++)
#define fb(i,s,f) for(int i=(s)-1;i>=f;i--)
#define ffi(i,s,f) for(int i=s;i<=f;i++)
#define fbi(i,s,f) for(int i=s;i>=f;i--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;
using ti = tuple<int,int,int>;
const int maxn=2e5+10;
int n,q;
int a[maxn];
int inv[maxn];
int veci[maxn];
int segt[4*maxn];
ti upit[maxn];
int res[maxn];
void update(int t,int v,int ind=1,int l=1,int r=n){
if(l==r){
segt[ind]=v;
return;
}
int mid=l+(r-l)/2;
if(t<=mid) update(t,v,2*ind,l,mid);
else update(t,v,2*ind+1,mid+1,r);
segt[ind]=segt[2*ind]+segt[2*ind+1];
}
int qry(int tl,int tr,int ind=1,int l=1,int r=n){
if(tl>tr) return 0;
if(tl<=l && r<=tr) return segt[ind];
int mid=l+(r-l)/2;
int ret=0;
if(tl<=mid) ret+=qry(tl,tr,2*ind,l,mid);
if(tr>mid) ret+=qry(tl,tr,2*ind+1,mid+1,r);
return ret;
}
int pronadji(int x){
int l=1,r=n;
int ret=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(qry(1,mid)>=x){
ret=mid;
r=mid-1;
}else l=mid+1;
}
return ret;
}
bool pomeri(){
int lik=pronadji(n/2+1);
int kraj=inv[lik]+qry(lik,lik)-1;
int prosli=inv[lik]+n/2+1-qry(1,lik-1)-1;
if(qry(a[prosli],a[prosli])!=0) return true;
update(lik,n/2+1-qry(1,lik-1)-1);
int tren=veci[prosli];
while(tren<=kraj){
update(a[prosli],tren-prosli);
prosli=tren;
tren=veci[tren];
}
update(a[prosli],kraj+1-prosli);
return false;
}
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
inv[a[i]]=i;
}
for(int i=1;i<=q;i++){
int t,ind;
cin>>t>>ind;
upit[i]={t,ind,i};
}
sort(upit+1,upit+q+1);
stack<int> stek;
for(int i=n;i>0;i--){
while(!stek.empty() && a[stek.top()]<a[i]) stek.pop();
if(stek.empty()) veci[i]=n+1;
else veci[i]=stek.top();
stek.push(i);
}
int tren=1;
int prosli=-1;
while(tren<=n/2){
if(prosli!=-1){
update(a[prosli],tren-prosli);
}
prosli=tren;
tren=veci[tren];
}
update(a[prosli],n/2+1-prosli);
tren=n/2+1;
prosli=-1;
while(tren<=n){
if(prosli!=-1) update(a[prosli],tren-prosli);
prosli=tren;
tren=veci[tren];
}
update(a[prosli],n+1-prosli);
int tu=0;
while(get<0>(upit[tu])==0){
res[get<2>(upit[tu])]=a[get<1>(upit[tu])];
tu++;
}
return;
for(int t=1;tu<=q;t++){
while(tu<=q && t>=get<0>(upit[tu])){
auto [t,x,ind]=upit[tu];
int gde=pronadji(x);
int klk=x-qry(1,gde-1)-1;
res[ind]=a[inv[gde]+klk];
tu++;
}
if(pomeri()) t=maxn;
}
for(int i=1;i<=q;i++){
cout<<res[i]<<"\n";
}
}
int main(){
ios;
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
8016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
8444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
8016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
