oj.uz

Submission #49147

# Submission time Handle Problem Language Result Execution time Memory
49147 2018-05-22T19:39:23 Z 3zp Cake (CEOI14_cake) C++14
100 / 100
 1569 ms 18644 KB 
#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 -- ){
        while(S.size() > 11){
            auto it = S.end();
            it--;
            S.erase(it);
        }
        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());
            }
            if(S.find({-A[x],x}) != S.end()) 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

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:80: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:72: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:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
             ~~~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 11 ms 468 KB Output is correct
5 Correct 25 ms 1252 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 1252 KB Output is correct
2 Correct 441 ms 1252 KB Output is correct
3 Correct 480 ms 1252 KB Output is correct
4 Correct 249 ms 1272 KB Output is correct
5 Correct 688 ms 2188 KB Output is correct
6 Correct 555 ms 2188 KB Output is correct
7 Correct 573 ms 2188 KB Output is correct
8 Correct 270 ms 2188 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 7308 KB Output is correct
2 Correct 264 ms 7308 KB Output is correct
3 Correct 246 ms 7308 KB Output is correct
4 Correct 3 ms 7308 KB Output is correct
5 Correct 537 ms 16200 KB Output is correct
6 Correct 516 ms 16200 KB Output is correct
7 Correct 317 ms 16200 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 16200 KB Output is correct
2 Correct 78 ms 16200 KB Output is correct
3 Correct 164 ms 16200 KB Output is correct
4 Correct 208 ms 16200 KB Output is correct
5 Correct 289 ms 16200 KB Output is correct
6 Correct 323 ms 16200 KB Output is correct
7 Correct 342 ms 16200 KB Output is correct
8 Correct 336 ms 16200 KB Output is correct
9 Correct 1569 ms 17468 KB Output is correct
10 Correct 979 ms 17468 KB Output is correct
11 Correct 1078 ms 17468 KB Output is correct
12 Correct 1415 ms 17468 KB Output is correct
13 Correct 1340 ms 18644 KB Output is correct