oj.uz

Submission #49145

# Submission time Handle Problem Language Result Execution time Memory
49145 2018-05-22T19:30:46 Z 3zp Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 19480 KB 
#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++){
        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

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++){
                            ~~^~~~~~~~~~
cake.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~
cake.cpp:64: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:84: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 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 12 ms 488 KB Output is correct
5 Correct 29 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 1168 KB Output is correct
2 Correct 442 ms 1304 KB Output is correct
3 Correct 615 ms 1304 KB Output is correct
4 Correct 312 ms 1304 KB Output is correct
5 Correct 963 ms 2016 KB Output is correct
6 Correct 654 ms 2016 KB Output is correct
7 Correct 667 ms 2016 KB Output is correct
8 Correct 382 ms 2152 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 7284 KB Output is correct
2 Correct 283 ms 7284 KB Output is correct
3 Correct 299 ms 7284 KB Output is correct
4 Correct 3 ms 7284 KB Output is correct
5 Correct 521 ms 16148 KB Output is correct
6 Correct 544 ms 16148 KB Output is correct
7 Correct 311 ms 16148 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 16148 KB Output is correct
2 Correct 101 ms 16148 KB Output is correct
3 Correct 193 ms 16148 KB Output is correct
4 Correct 288 ms 16148 KB Output is correct
5 Correct 564 ms 16148 KB Output is correct
6 Correct 390 ms 16148 KB Output is correct
7 Correct 413 ms 16148 KB Output is correct
8 Correct 427 ms 16148 KB Output is correct
9 Execution timed out 2065 ms 17684 KB Time limit exceeded
10 Correct 1225 ms 17684 KB Output is correct
11 Correct 1348 ms 17684 KB Output is correct
12 Execution timed out 2050 ms 17684 KB Time limit exceeded
13 Correct 1693 ms 19480 KB Output is correct