oj.uz

답안 #49146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49146 2018-05-22T19:33:18 Z 3zp 케이크 (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 18148 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 -- ){
        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:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
cake.cpp: In function 'int main()':
cake.cpp:74: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:66: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:86: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 13 ms 492 KB Output is correct
5 Correct 50 ms 1180 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 767 ms 1180 KB Output is correct
2 Correct 413 ms 1196 KB Output is correct
3 Correct 504 ms 1196 KB Output is correct
4 Correct 276 ms 1252 KB Output is correct
5 Correct 877 ms 2020 KB Output is correct
6 Correct 636 ms 2152 KB Output is correct
7 Correct 549 ms 2152 KB Output is correct
8 Correct 378 ms 2152 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 7292 KB Output is correct
2 Correct 278 ms 7292 KB Output is correct
3 Correct 271 ms 7292 KB Output is correct
4 Correct 2 ms 7292 KB Output is correct
5 Correct 516 ms 16008 KB Output is correct
6 Correct 516 ms 16140 KB Output is correct
7 Correct 300 ms 16140 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 16140 KB Output is correct
2 Correct 98 ms 16140 KB Output is correct
3 Correct 239 ms 16140 KB Output is correct
4 Correct 246 ms 16140 KB Output is correct
5 Correct 340 ms 16140 KB Output is correct
6 Correct 699 ms 16140 KB Output is correct
7 Correct 397 ms 16140 KB Output is correct
8 Correct 420 ms 16140 KB Output is correct
9 Execution timed out 2059 ms 16820 KB Time limit exceeded
10 Correct 1242 ms 16820 KB Output is correct
11 Correct 1676 ms 16820 KB Output is correct
12 Execution timed out 2005 ms 16820 KB Time limit exceeded
13 Correct 1539 ms 18148 KB Output is correct