Submission #224966

# Submission time Handle Problem Language Result Execution time Memory
224966 2020-04-19T07:26:29 Z brcode Cake (CEOI14_cake) C++14
15 / 100
1596 ms 18552 KB
#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);
            
            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<<" "<<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<<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));
                }
                
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 17 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 612 ms 5112 KB Output is correct
2 Correct 500 ms 5240 KB Output is correct
3 Correct 562 ms 5240 KB Output is correct
4 Correct 454 ms 5240 KB Output is correct
5 Correct 668 ms 5984 KB Output is correct
6 Correct 585 ms 6264 KB Output is correct
7 Correct 596 ms 6136 KB Output is correct
8 Correct 476 ms 6392 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 372 ms 5880 KB Output isn't correct
2 Correct 334 ms 5880 KB Output is correct
3 Correct 334 ms 5752 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 464 ms 11512 KB Output is correct
6 Incorrect 455 ms 11696 KB Output isn't correct
7 Correct 437 ms 11392 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 1144 KB Output isn't correct
2 Incorrect 130 ms 1144 KB Output isn't correct
3 Incorrect 248 ms 3320 KB Output isn't correct
4 Incorrect 228 ms 3448 KB Output isn't correct
5 Incorrect 352 ms 2008 KB Output isn't correct
6 Correct 465 ms 5248 KB Output is correct
7 Correct 532 ms 3016 KB Output is correct
8 Correct 370 ms 6520 KB Output is correct
9 Correct 1596 ms 16532 KB Output is correct
10 Incorrect 1107 ms 5368 KB Output isn't correct
11 Incorrect 1249 ms 7104 KB Output isn't correct
12 Incorrect 1471 ms 15300 KB Output isn't correct
13 Incorrect 1278 ms 18552 KB Output isn't correct