Submission #49144

#	Time	Username	Problem	Language	Result	Execution time	Memory
49144		3zp	Cake (CEOI14_cake)	C++14	83.33 / 100	2070 ms	42600 KiB

cake

#include<bits/stdc++.h>
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++){
        cin >> 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;
            cin >> 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;
            cin >> x;
            if(x < a){
                cout << fin1(2,a+1,n+1,cnt(1,0,a-1,x,a-1)) - x - 1 << endl;
            }
            else{
                cout << x - fin2(1,0,a-1,cnt(2,a+1,n+1,a+1,x)) - 1 << endl;
            }
        }
    }

}

Compilation message (stderr)

cake.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
cake.cpp: In function 'int main()':
cake.cpp:72:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i++){
                            ~~^~~~~~~~~~

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