oj.uz

Submission #49143

# Submission time Handle Problem Language Result Execution time Memory
49143 2018-05-22T19:24:44 Z 3zp Cake (CEOI14_cake) C++14
30 / 100
 1800 ms 70076 KB 
#include<bits/stdc++.h>
using namespace std;
int A[100009];
int T[100009];
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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 436 KB Output is correct
4 Correct 15 ms 620 KB Output is correct
5 Correct 37 ms 1348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 5620 KB Output is correct
2 Correct 622 ms 10296 KB Output is correct
3 Correct 790 ms 14700 KB Output is correct
4 Correct 578 ms 19152 KB Output is correct
5 Correct 1242 ms 24764 KB Output is correct
6 Correct 969 ms 30000 KB Output is correct
7 Correct 1032 ms 34632 KB Output is correct
8 Correct 620 ms 39748 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 49264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 68 ms 50580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 73 ms 51348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 2 ms 51348 KB Output is correct
5 Runtime error 143 ms 52028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 106 ms 52636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 78 ms 53516 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 53516 KB Output is correct
2 Correct 115 ms 53516 KB Output is correct
3 Runtime error 53 ms 53516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 46 ms 53516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 403 ms 53516 KB Output is correct
6 Runtime error 79 ms 54308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 502 ms 54308 KB Output is correct
8 Runtime error 120 ms 60144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 121 ms 60592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 1465 ms 60592 KB Output is correct
11 Correct 1800 ms 66028 KB Output is correct
12 Runtime error 127 ms 69308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 134 ms 70076 KB Execution killed with signal 11 (could be triggered by violating memory limits)