oj.uz

답안 #224742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224742 2020-04-18T17:24:23 Z brcode 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 9536 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];
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 = 1;
                
                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>=min(n-rev[curr],ub);i--){
                   // cout<<123<<" "<<i<<" "<<ranks[i]<<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=val;i>=min(n-rev[curr],ub);i--){
                    ranks[i-1] = ranks[i];
                    rev[ranks[i-1]] = i-1;
                }
                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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2097 ms 1016 KB Time limit exceeded
2 Execution timed out 2087 ms 1056 KB Time limit exceeded
3 Execution timed out 2087 ms 1024 KB Time limit exceeded
4 Execution timed out 2095 ms 1144 KB Time limit exceeded
5 Execution timed out 2087 ms 1408 KB Time limit exceeded
6 Execution timed out 2094 ms 1528 KB Time limit exceeded
7 Execution timed out 2082 ms 1528 KB Time limit exceeded
8 Execution timed out 2094 ms 1528 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 607 ms 4912 KB Output isn't correct
2 Incorrect 682 ms 4856 KB Output isn't correct
3 Incorrect 627 ms 4856 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Incorrect 912 ms 9464 KB Output isn't correct
6 Incorrect 1236 ms 9536 KB Output isn't correct
7 Incorrect 1197 ms 9436 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 1068 KB Time limit exceeded
2 Execution timed out 2091 ms 1280 KB Time limit exceeded
3 Execution timed out 2085 ms 2320 KB Time limit exceeded
4 Execution timed out 2098 ms 2176 KB Time limit exceeded
5 Execution timed out 2095 ms 1312 KB Time limit exceeded
6 Execution timed out 2070 ms 2936 KB Time limit exceeded
7 Execution timed out 2080 ms 1296 KB Time limit exceeded
8 Execution timed out 2099 ms 3704 KB Time limit exceeded
9 Execution timed out 2092 ms 8056 KB Time limit exceeded
10 Execution timed out 2094 ms 1272 KB Time limit exceeded
11 Execution timed out 2098 ms 1272 KB Time limit exceeded
12 Execution timed out 2089 ms 6904 KB Time limit exceeded
13 Execution timed out 2089 ms 9080 KB Time limit exceeded