Submission #224984

#	Time	Username	Problem	Language	Result	Execution time	Memory
224984		brcode	Cake (CEOI14_cake)	C++14	100 / 100	1604 ms	18552 KiB

cake

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int n,k;
const int MAXN = 5e5+5;
pair<int,int> arr[MAXN];
int ranks[MAXN];
int rev[MAXN];
int cnt = -1e9;
struct segmenttree{
    pair<int,int> seg[4*MAXN];
    void build(int curr,int l,int r){
        if(l==r){
            seg[curr] = make_pair(rev[l],0);
            if(seg[curr].first == n-11){
                seg[curr].second = -1e9;
            }
            return;
        }
        int mid = (l+r)/2;
        build(2*curr,l,mid);
        build(2*curr+1,mid+1,r);
        seg[curr] = max(seg[2*curr],seg[2*curr+1]);
    }
    pair<int,int> query(int curr,int l,int r,int tl,int tr){
        if(l>tr||r<tl){
            return make_pair(-1e9,-1e9);
        }
        if(tl<=l && r<=tr){
            return seg[curr];
        }
        int mid = (l+r)/2;
        return max(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
    }
    int lmost(int curr,int l,int r,pair<int,int> val){
        
        if(seg[curr]<val){
            return r+1;
        }
        if(l==r){
            return l;
        }
        int mid = (l+r)/2;
        if(seg[2*curr]>val){
            return lmost(2*curr,l,mid,val);
        }else if(seg[2*curr+1]>val){
            return lmost(2*curr+1,mid+1,r,val);
        }else{
            return r+1;
        }
    }
    int rmost(int curr,int l,int r,pair<int,int> val){
        if(seg[curr]<val){
            return l-1;
        }
        if(l==r){
            return l;
        }
        int mid = (l+r)/2;
        if(seg[2*curr+1]>val){
            return rmost(2*curr+1,mid+1,r,val);
        }else if(seg[2*curr]>val){
            return rmost(2*curr,l,mid,val);
        }else{
            return l-1;
        }
    }
    void update(int curr,int l,int r,int ind ,pair<int,int> val){
        if(l==r){
            seg[curr] = val;
            return;
        }
        int mid = (l+r)/2;
        if(ind<=mid){
            update(2*curr,l,mid,ind,val);
        }else{
            update(2*curr+1,mid+1,r,ind,val);
        }
        seg[curr] = max(seg[2*curr],seg[2*curr+1]);
    }
} segl,segr;

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i].first;
        arr[i].second = i;
    }
    sort(arr+1,arr+n+1);
    for(int i=1;i<=n;i++){
        ranks[i] = arr[i].second;
        rev[arr[i].second] = i;//what rank is ith position
    }
    if(k!=1){
        segl.build(1,1,k-1);
    }
    if(k!=n){
        segr.build(1,k+1,n);
    }
    int q;
    cin>>q;
    int ub = max(1,n-11);
    while(q--){
        char s;
        cin>>s;
        if(s=='F'){
            int x;
            cin>>x;
            if(x==k){
                cout<<0<<endl;
                continue;
            }
            if(x<k){
                auto temp = segl.query(1,1,k-1,x,k-1);
                int temp2 = n+1;
                
                if(temp.first!=n){
                    temp2 = segr.lmost(1,k+1,n,temp);
                }
                //cout<<x<<" "<<temp2<<endl;
                cout<<temp2-x-1<<endl;
            }else{
                auto temp = segr.query(1,k+1,n,k+1,x);
                int temp2 = 0;
               // cout<<123<<" "<<temp<<endl;
                if(temp.first!=n){
                    temp2 = segl.rmost(1,1,k-1,temp);
                }
               // cout<<123<<" "<<temp.first<<" "<<temp.second<<endl;
                cout<<x-temp2-1<<endl;
            }
        }else{
            int curr,val;
            cin>>curr>>val;
            //cout<<curr<<" "<<val<<endl;
            val = n-val+1;
           // cout<<curr<<" "<<val<<endl;
           //cout<<1234<<" "<<curr<<" "<<val<<endl;
           // cout<<1234<<" "<<val<<" "<<rev[curr]<<endl;
                for(int i=val;i>max(ub,rev[curr]);i--){
                   // cout<<123<<" "<<ranks[i]<<" "<<i-1<<endl;
                    //cout<<1234<<" "<<i<<" "<<ranks[i]<<" "<<min(rev[curr],min(10,n))<<endl;
                    if(ranks[i] == k){
                        continue;
                    }
                    if(ranks[i]<k){
                        if(i-1 == n-11){
                            cnt++;
                            
                            segl.update(1,1,k-1,ranks[i],make_pair(i-1,cnt));
                        }else{
                            segl.update(1,1,k-1,ranks[i],make_pair(i-1,0));

                        }
                        
                    }else{
                        if(i-1 == n-11){
                            cnt++;
                            segr.update(1,k+1,n,ranks[i],make_pair(i-1,cnt));
                        }else{
                            segr.update(1,k+1,n,ranks[i],make_pair(i-1,0));
                        }
                    }
                    
                }
                for(int i=max(ub,rev[curr])+1;i<=val;i++){
                    
                    ranks[i-1] = ranks[i];
                    rev[ranks[i]] = i-1;
                    //cout<<(i-1)<<" "<<ranks[i-1]<<endl;
                }
                
                ranks[val] = curr;
                rev[curr] = val;
              //  cout<<endl;
           /*for(int i=1;i<=n;i++){
                cout<<rev[i]<<" ";
            }
            cout<<endl;
            for(int i=1;i<=n;i++){
               cout<<ranks[i]<<" ";
            }
            cout<<endl;*/
            if(curr==k){
                    continue;
                }
                if(curr<k){
                    segl.update(1,1,k-1,curr,make_pair(val,0));
                }else{
                    segr.update(1,k+1,n,curr,make_pair(val,0));
                }
                
        }
    }
}

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