Submission #224762

#	Time	Username	Problem	Language	Result	Execution time	Memory
224762		brcode	Cake (CEOI14_cake)	C++14	0 / 100	1384 ms	13816 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];
struct segmenttree{
    int seg[4*MAXN];
    void build(int curr,int l,int r){
        if(l==r){
            seg[curr] = rev[l];
            
            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]);
    }
    int query(int curr,int l,int r,int tl,int tr){
        if(l>tr||r<tl){
            return -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,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,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 ,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-10);
    while(q--){
        char s;
        cin>>s;
        if(s=='F'){
            int x;
            cin>>x;
            if(x==k){
                cout<<0<<endl;
                continue;
            }
            if(x<k){
                int temp = segl.query(1,1,k-1,x,k-1);
                int temp2 = n+1;
                
                if(temp!=n){
                    temp2 = segr.lmost(1,k+1,n,temp);
                }
                //cout<<x<<" "<<temp2<<endl;
                cout<<temp2-x-1<<endl;
            }else{
                int temp = segr.query(1,k+1,n,k+1,x);
                int temp2 = 0;
               // cout<<123<<" "<<temp<<endl;
                if(temp!=n){
                    temp2 = segl.rmost(1,1,k-1,temp);
                }
               // cout<<123<<" "<<temp2<<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<<rev[curr]<<endl;
                for(int i=val;i>=max(n-rev[curr],ub);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){
                        segl.update(1,1,k-1,ranks[i],i-1);
                        
                    }else{
                        segr.update(1,k+1,n,ranks[i],i-1);
                    }
                    
                }
                for(int i=max(n-rev[curr],ub)+1;i<=val;i++){
                    ranks[i-1] = ranks[i];
                    rev[ranks[i-1]] = i-1;
                    //cout<<(i-1)<<" "<<ranks[i-1]<<endl;
                }
                
                ranks[val] = curr;
                rev[curr] = val;
            
            if(curr==k){
                    continue;
                }
                if(curr<k){
                    segl.update(1,1,k-1,curr,val);
                }else{
                    segr.update(1,k+1,n,curr,val);
                }
        }
    }
}

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