Submission #49146

#	Time	Username	Problem	Language	Result	Execution time	Memory
49146		3zp	Cake (CEOI14_cake)	C++14	83.33 / 100	2059 ms	18148 KiB

cake

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")

using namespace std;
int A[2000009];
int T[2000009];
void build(int x, int l, int r){
    if(l == r){
        T[x] = A[l];
        return;
    }
    int mid = (l + r) /2;
    build(2*x+1, l , mid);
    build(2*x+2, mid + 1, r );
    T[x] = max(T[2*x+2], T[2*x+1]);
}
void upd(int x, int l, int r, int p, int v){
    if(l > p || r < p) return;
    if(l == r){
        T[x] = v;
        return;
    }
    int mid = (l + r)/2;
    upd(2*x+1,l,mid,p,v);
    upd(2*x+2,mid+1,r,p,v);
    T[x] = max(T[2*x+2], T[2*x+1]);
}
int fin1(int x, int l, int r, int A){
    if(l == r) return l;
    int mid = (l + r)/2;
    if(T[2*x+1] < A) return fin1(2*x+2, mid+1,r, A);
    else return fin1(2*x+1, l, mid, A);
}
int fin2(int x, int l, int r, int A){
    if(l == r) return l;
    int mid = (l + r)/2;
    if(T[2*x+2] >= A) return fin2(2*x+2, mid+1,r, A);
    else return fin2(2*x+1, l, mid, A);
}
int cnt(int x, int l, int r, int a, int b){
    if(l > b || r < a) return 0;
    if(l >= a && r <= b) return T[x];
    int mid = (l + r)/2;
    return max(cnt(2*x+1,l,mid,a,b),
            cnt(2*x+2,mid+1,r,a,b));
}
set<pair<int,int> > S;
main(){
    int n, a;
    cin >> n >> a;
    for(int i = 1; i <= n; i++){
        scanf("%d",&A[i]);
        S.insert({-A[i], i});
    }
    A[n + 1] = 1e9;
    A[0] = 1e9;
    build(1,0,a-1);
    build(2,a+1,n+1);
    int q;
    cin >> q;
    while(q -- ){
        char c;
        cin >> c;
        if(c == 'E'){
            int x , e;
            scanf("%d%d",&x,&e);
            vector<int> v;
            for(int i = 0; i < e-1; i++){
                v.push_back((*S.begin()).second);
                S.erase(S.begin());
            }
            S.erase(S.find({-A[x],x}));
            A[x] = (-((*S.begin()).first) + 1);
            for(int i = 0; i < v.size(); i++){
                A[v[i]] ++;
                upd(1,0,a-1,v[i],A[v[i]]);
                upd(2,a+1,n+1,v[i],A[v[i]]);
                S.insert({-A[v[i]],v[i]});
            }
            upd(1,0,a-1,x,A[x]);
            upd(2,a+1,n+1,x,A[x]);
            S.insert({-A[x],x});
        }
        else{
            int x;
            scanf("%d",&x);
            if(x < a){
                printf("%d\n",fin1(2,a+1,n+1,cnt(1,0,a-1,x,a-1)) - x - 1 );
            }
            else{
                 printf("%d\n", x - fin2(1,0,a-1,cnt(2,a+1,n+1,a+1,x)) - 1 );
            }
        }
    }

}

Compilation message (stderr)

cake.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
cake.cpp: In function 'int main()':
cake.cpp:74:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i++){
                            ~~^~~~~~~~~~
cake.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~
cake.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&x,&e);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
             ~~~~~^~~~~~~~~

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