제출 #1226221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226221		Warinchai	케이크 (CEOI14_cake)	C++20	100 / 100	357 ms	7164 KiB

cake

#include<bits/stdc++.h>
using namespace std;
int ar[250005];
int n,a;
struct segtree{
    int mx[1000005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return void(mx[i]=val);
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        mx[i]=max(mx[i*2],mx[i*2+1]);
    }
    int fr(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l||mx[i]<=val)return 0;
        if(st==en)return st;
        int m=(st+en)/2;
        int temp=fr(st,m,i*2,l,r,val);
        if(temp==0)return fr(m+1,en,i*2+1,l,r,val);
        return temp;
    }
    int fl(int st,int en,int i,int l,int r,int val){
        //cerr<<st<<" "<<en<<" "<<mx[i]<<" "<<"\n";
        if(st>r||en<l||mx[i]<=val)return 0;
        if(st==en)return st;
        //cerr<<"pass\n";
        int m=(st+en)/2;
        int temp=fl(m+1,en,i*2+1,l,r,val);
        if(temp==0)return fl(st,m,i*2,l,r,val);
        else return temp;
    }
    int fmx(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return mx[i];
        int m=(st+en)/2;
        return max(fmx(st,m,i*2,l,r),fmx(m+1,en,i*2+1,l,r));
    }
    void build(int st,int en,int i){
        if(st==en)return void(mx[i]=ar[st]);
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        mx[i]=max(mx[i*2],mx[i*2+1]);
    }
}tr;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>a;
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++)cin>>ar[i],v.push_back({ar[i],i});
    sort(v.begin(),v.end());
    vector<int>most;
    for(int i=0;i<v.size();i++){
        ar[v[i].second]=i+1;
    }
    for(int i=0;i<10;i++){
        if(i>=v.size())break;
        most.push_back(v[v.size()-i-1].second);
    }
    //for(auto x:most)cerr<<x<<" ";
    //cerr<<"\n";
    tr.build(1,n,1);
    int cur=n;
    int q;cin>>q;
    for(int i=0;i<q;i++){
        char x;cin>>x;
        if(x=='E'){
            int i,e;cin>>i>>e;
            vector<int>temp;
            int j=0;
            for(;j<e-1;j++){
                temp.push_back(most[j]);
            }
            temp.push_back(i);
            while(temp.size()<(min(10,n))){
                if(most[j]!=i)temp.push_back(most[j]);
                j++;
            }
            most=temp;
            //cerr<<"most: ";
            //for(auto x:most)cerr<<x<<" ";
            //cerr<<"\n";
            for(int i=most.size()-1;i>=0;i--){
                tr.upd(1,n,1,most[i],cur+most.size()-i);
            }
            cur+=most.size();
            //for(int i=1;i<=n;i++)cerr<<tr.fmx(1,n,1,i,i)<<' ';
            //cerr<<"\n";
        }else{
            int b;cin>>b;
            if(b>a){
                int temp=tr.fmx(1,n,1,a+1,b);
                int id=0;
                if(tr.fmx(1,n,1,1,a-1)<temp){
                    id=0;
                }else{
                    id=tr.fl(1,n,1,1,a-1,temp);
                }
                //cerr<<"ql:"<<b<<" "<<temp<<" "<<id<<"\n";
                cout<<b-id-1<<"\n";
            }else if(b<a){
                int temp=tr.fmx(1,n,1,b,a-1);
                int id=0;
                if(tr.fmx(1,n,1,a+1,n)<temp){
                    id=n+1;
                }else{
                    id=tr.fr(1,n,1,a+1,n,temp);
                }
                //cerr<<"qr:"<<b<<" "<<temp<<" "<<id<<"\n";
                cout<<id-b-1<<"\n";
            }else{
                cout<<"0\n";
            }
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50