oj.uz

Submission #49144

# Submission time Handle Problem Language Result Execution time Memory
49144 2018-05-22T19:25:47 Z 3zp Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 42600 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++){
        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 2 ms 248 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 13 ms 508 KB Output is correct
5 Correct 36 ms 1164 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 1164 KB Output is correct
2 Correct 551 ms 1164 KB Output is correct
3 Correct 702 ms 1164 KB Output is correct
4 Correct 552 ms 1180 KB Output is correct
5 Correct 1291 ms 2132 KB Output is correct
6 Correct 895 ms 2132 KB Output is correct
7 Correct 880 ms 2132 KB Output is correct
8 Correct 604 ms 2152 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 7816 KB Output is correct
2 Correct 334 ms 8436 KB Output is correct
3 Correct 346 ms 9040 KB Output is correct
4 Correct 3 ms 9040 KB Output is correct
5 Correct 578 ms 19496 KB Output is correct
6 Correct 675 ms 21104 KB Output is correct
7 Correct 436 ms 22460 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 22460 KB Output is correct
2 Correct 108 ms 22460 KB Output is correct
3 Correct 237 ms 22460 KB Output is correct
4 Correct 272 ms 22460 KB Output is correct
5 Correct 436 ms 22460 KB Output is correct
6 Correct 755 ms 22460 KB Output is correct
7 Correct 473 ms 22460 KB Output is correct
8 Correct 494 ms 22460 KB Output is correct
9 Execution timed out 2056 ms 31308 KB Time limit exceeded
10 Correct 1246 ms 31308 KB Output is correct
11 Correct 1745 ms 31308 KB Output is correct
12 Execution timed out 2070 ms 33236 KB Time limit exceeded
13 Execution timed out 2025 ms 42600 KB Time limit exceeded