Submission #797653

#	Time	Username	Problem	Language	Result	Execution time	Memory
797653		FEDIKUS	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	568 ms	40724 KiB

Main

#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=1e6+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 ind=1,int l=1,int r=n){
    if(l==r) return l;
    int mid=l+(r-l)/2;
    if(segt[2*ind]>=x) return pronadji(x,2*ind,l,mid);
    else return pronadji(x-segt[2*ind],2*ind+1,mid+1,r);
}

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++;
    }

    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=1e9+10;
    }
    for(int i=1;i<=q;i++){
        cout<<res[i]<<"\n";
    }
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25