Submission #647718

#	Time	Username	Problem	Language	Result	Execution time	Memory
647718		mosiashvililuka	Abracadabra (CEOI22_abracadabra)	C++14	0 / 100	621 ms	27432 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],ans[1000009],rg[200009],fen[200009],seg[800009],seg2[800009],l,r,z,zz,za,Af[200009];
vector <pair <int, int> > v[200009];
deque <int> de;
void updfen(int q, int w){
    while(q<=200003){
        fen[q]+=w;
        q=q+(q&(-q));
    }
}
int readfen(int q){
    int sm=0;
    while(q>0){
        sm+=fen[q];
        q=q-(q&(-q));
    }
    return sm;
}
void pushdown(int q, int w, int rr){
    if(q!=w){
        seg2[rr*2]+=seg2[rr];
        seg2[rr*2+1]+=seg2[rr];
    }
    seg[rr]+=seg2[rr];
    seg2[rr]=0;
}
void upd(int q, int w, int rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]+=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    seg[rr]=max(seg[rr*2],seg[rr*2+1]);
}
void read(int q, int w, int rr){
    pushdown(q,w,rr);
    if(q==w){
        z=q;
        return;
    }
    pushdown(q,(q+w)/2,rr*2);
    pushdown((q+w)/2+1,w,rr*2+1);
    if(seg[rr*2]>=zz){
        read(q,(q+w)/2,rr*2);
    }else{
        read((q+w)/2+1,w,rr*2+1);
    }
}
void ADD(int i){
    int q=f[i],w=rg[i]-i;
    updfen(q,w);
    l=q;r=a;z=w;
    upd(1,za,1);
}
void REM(int i){
    int q=f[i],w=rg[i]-i;
    updfen(q,-w);
    l=q;r=a;z=-w;
    upd(1,za,1);
}
void answer(int TA){
    for(vector <pair <int, int> >::iterator it=v[TA].begin(); it!=v[TA].end(); it++){
        l=1;r=a;zz=(*it).first;z=0;
        read(1,za,1);
        ii=Af[z];
        i=readfen(f[ii]-1)+1;
        c=(zz-i)+ii;
        ans[(*it).second]=f[c];
    }
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>tes;
    for(i=1; i<=a; i++) cin>>f[i];
    for(i=1; i<=a; i++){
        Af[f[i]]=i;
    }
    for(t=1; t<=tes; t++){
        cin>>c>>d;c=min(c,a);
        v[c].push_back({d,t});
    }
    za=1;
    while(za<a) za*=2;
    for(vector <pair <int, int> >::iterator it=v[0].begin(); it!=v[0].end(); it++){
        ans[(*it).second]=f[(*it).first];
    }
    for(i=a; i>=1; i--){
        while(de.size()>0&&f[de.back()]<f[i]) de.pop_back();
        if(de.size()==0){
            rg[i]=a+1;
        }else{
            rg[i]=de.back();
        }
        de.push_back(i);
    }
    i=1;
    while(i<=a){
        ADD(i);i=rg[i];
    }
    for(int TA=1; TA<=a; TA++){
        l=1;r=a;zz=a/2;z=0;
        read(1,za,1);
        ii=Af[z];
        i=readfen(f[ii]-1)+1;c=rg[ii]-ii;
        if(i+c-1<=a/2){
            answer(TA);
            continue;
        }
        REM(ii);
        c=(a/2-i)+ii+1;
        int EA=rg[ii];
        rg[ii]=c;
        ADD(ii);
        while(c<=a&&/*f[c]<f[ii]*/c<EA){
            ADD(c);c=rg[c];
        }
        answer(TA);
    }
    for(t=1; t<=tes; t++){
        cout<<ans[t]<<"\n";
    }
    return 0;
}

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