Submission #1054511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054511		gagik_2007	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	2079 ms	54756 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=200007;
ll n,m,k;
int a[N];
int d[N];
int ind[N];
bool met[N];
set<int>s;
int curlen=0;
pair<int,int> t[4*N];
int tt[4*N];
vector<pair<pair<int,int>,int>>q;
int qi=0;

void build(int v, int tl, int tr){
    if(tl==tr){
        t[v]={a[tl],tl};
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
}

void build2(int v, int tl, int tr){
    if(tl==tr){
        tt[v]=d[tl];
    }
    else{
        int tm=(tl+tr)/2;
        build2(2*v,tl,tm);
        build2(2*v+1,tm+1,tr);
        tt[v]=tt[2*v]+tt[2*v+1];
    }
}

void update(int v, int tl, int tr, int ind, int val){
    if(tl==tr){
        tt[v]=val;
    }
    else{
        int tm=(tl+tr)/2;
        if(ind<=tm){
            update(2*v,tl,tm,ind,val);
        }
        else{
            update(2*v+1,tm+1,tr,ind,val);
        }
        tt[v]=tt[2*v]+tt[2*v+1];
    }
}

int getsum(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l&&tr==r){
        return tt[v];
    }
    else{
        int tm=(tl+tr)/2;
        return getsum(2*v,tl,tm,l,min(r,tm))+
            getsum(2*v+1,tm+1,tr,max(tm+1,l),r);
    }
}

int binsearch(int indd){
    int l=1,r=n+1;
    while(l<r){
        int mid=(l+r)/2;
        if(getsum(1,1,n,mid,n)>indd){
            l=mid+1;
        }
        else{
            r=mid;
        }
    }
    return l-1;
}

pair<int,int> getmax(int v, int tl, int tr, int l, int r){
    if(l>r)return {0,0};
    if(tl==l&&tr==r){
        return t[v];
    }
    else{
        int tm=(tl+tr)/2;
        return max(getmax(2*v,tl,tm,l,min(r,tm)),
            getmax(2*v+1,tm+1,tr,max(tm+1,l),r));
    }
}

int stepcnt=0;

void step(vector<int>&ans){
    while(qi!=m&&q[qi].ff.ff==stepcnt){
        int indd=n-q[qi].ff.ss-1;
        int cmp=binsearch(indd);
        int cmpind=getsum(1,1,n,cmp,n)-1;
        ans[q[qi].ss]=a[ind[cmp]-(cmpind-indd)];
        qi++;
    }
    stepcnt++;
    // cout<<"step"<<endl;
    while(curlen+d[-(*s.begin())]<=n/2){
        curlen+=d[-(*s.begin())];
        s.erase(s.begin());
    }
    int v=-(*s.begin());
    int i=ind[v];
    int len=d[v];
    // cout<<v<<" "<<i<<" "<<len<<endl;
    int l=ind[v]-d[v]+1;
    int r=n/2-curlen+l-1;
    d[v]=i-r;
    update(1,1,n,v,d[v]);
    // cout<<l<<" "<<r<<endl;
    while(l<=r){
        pair<int,int>e=getmax(1,0,n-1,l,r);
        int mx=e.ff;
        int mxi=e.ss;
        int newlen=mxi-l+1;
        d[mx]=newlen;
        update(1,1,n,mx,d[mx]);
        ind[mx]=mxi;
        s.insert(-mx);
        l=mxi+1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Ainput.txt","r",stdin);
    // freopen("Aoutput.txt","w",stdout);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[n-i-1];
    }
    build(1,0,n-1);
    int lsti=-1;
    int mx=n;
    int i=0;
    while(i!=n){
        while(i!=n&&a[i]<mx){
            met[a[i]]=true;
            i++;
        }
        d[mx]=i-lsti;
        ind[mx]=i;
        s.insert(-mx);
        met[mx]=true;
        while(met[mx]){
            mx--;
        }
        lsti=i;
        i++;
    }
    build2(1,1,n);
    int t=0;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        y--;
        q.push_back({{x,y},i});
        // t=x;
    }
    sort(q.begin(),q.end());
    vector<int>ans(m,0);
    for(int i=0;i<n*5;i++){
        step(ans);
    }
    while(qi!=m){
        int indd=n-q[qi].ff.ss-1;
        int cmp=binsearch(indd);
        int cmpind=getsum(1,1,n,cmp,n)-1;
        ans[q[qi].ss]=a[ind[cmp]-(cmpind-indd)];
        qi++;
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void step(std::vector<int>&)':
Main.cpp:124:9: warning: unused variable 'len' [-Wunused-variable]
  124 |     int len=d[v];
      |         ^~~
Main.cpp: In function 'int main()':
Main.cpp:174:9: warning: unused variable 't' [-Wunused-variable]
  174 |     int t=0;
      |         ^

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