답안 #101805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101805 2019-03-20T10:34:39 Z rocketninja7 케이크 (CEOI14_cake) C++14
20 / 100
1018 ms 28816 KB
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
    int s, e, m, v, i;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), v(0){
        if(_s<_e){
            l=new node(s, m);
            r=new node(m+1, e);
        }
    }
    void update(int index, int val){
        if(s==e){
            v=val;
        }
        else{
            if(index<=m){
                l->update(index, val);
            }
            else{
                r->update(index, val);
            }
            if(l->v>r->v){
                v=l->v;
                i=l->i;
            }
            else{
                v=r->v;
                i=r->i;
            }
        }
    }
    int query(int si, int ei){
        if(si==s&&ei==e){
            return v;
        }
        if(ei<=m){
            return l->query(si, ei);
        }
        if(si>m){
            return r->query(si, ei);
        }
        return max(l->query(si, m), r->query(m+1, ei));
    }
    int query2(int val, int dir){
        if(s==e){
            return s;
        }
        if(dir==1){
            if(l->v<val){
                return r->query2(val, dir);
            }
            return l->query2(val, dir);
        }
        if(r->v<val){
            return l->query2(val, dir);
        }
        return r->query2(val, dir);
    }
};

int main(){
    int N, a;
    scanf("%d%d", &N, &a);
    int d[N+1];
    vector<pair<int, int> > best;
    node *lst=new node(0, a-1);
    node *rst=new node(a+1, N+1);
    for(int i=1;i<N+1;i++){
        scanf("%d", &d[i]);
        best.push_back(make_pair(-d[i], i));
        if(i<a){
            lst->update(i, d[i]);
        }
        else{
            rst->update(i, d[i]);
        }
    }
    sort(best.begin(), best.end());
    while(best.size()>10){
        best.pop_back();
    }
    int Q;
    scanf("%d", &Q);
    while(Q--){
        char op;
        scanf("\n%c", &op);
        if(op=='E'){
            int i, e;
            scanf("%d%d", &i, &e);
            if(N==1){
                continue;
            }
            e--;
            for(int j=0;j<best.size();j++){
                if(best[j].first==-d[i]){
                    best.erase(best.begin()+j);
                    break;
                }
            }
            for(int j=0;j<e;j++){
                if(best[j].second<a){
                    lst->update(best[j].second, -(--best[j].first));
                }
                else if(best[j].second>a){
                    rst->update(best[j].second, -(--best[j].first));
                }
                else{
                    --best[j].first;
                }
                d[best[j].second]++;
            }
            d[i]=(e>0?d[best[e-1].second]-1:d[best[e+1].second]+1);
            best.insert(best.begin()+e, make_pair(-d[i], i));
            if(best.size()>10){
                best.pop_back();
            }
            if(i<a){
                lst->update(i, d[i]);
            }
            else if(i>a){
                rst->update(i, d[i]);
            }
        }
        else{
            int b;
            scanf("%d", &b);
            if(b<a){
                printf("%d\n", rst->query2(lst->query(b, a-1), 1)-1-b);
            }
            else if(b>a){
                printf("%d\n", b-1-lst->query2(rst->query(a+1, b), -1));
            }
            else{
                printf("0\n");
            }
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:98:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<best.size();j++){
                         ~^~~~~~~~~~~~
cake.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &a);
     ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
cake.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &op);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &i, &e);
             ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:130:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 1536 KB Output is correct
2 Correct 176 ms 1656 KB Output is correct
3 Correct 246 ms 1704 KB Output is correct
4 Incorrect 180 ms 1588 KB Output isn't correct
5 Correct 431 ms 3256 KB Output is correct
6 Correct 253 ms 3200 KB Output is correct
7 Correct 268 ms 3288 KB Output is correct
8 Incorrect 199 ms 3200 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 11540 KB Output is correct
2 Correct 122 ms 11504 KB Output is correct
3 Correct 105 ms 11500 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 299 ms 27640 KB Output is correct
6 Correct 216 ms 27496 KB Output is correct
7 Correct 173 ms 27516 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 812 KB Output isn't correct
2 Correct 34 ms 1024 KB Output is correct
3 Correct 118 ms 5876 KB Output is correct
4 Incorrect 134 ms 6160 KB Output isn't correct
5 Incorrect 120 ms 900 KB Output isn't correct
6 Correct 186 ms 7916 KB Output is correct
7 Correct 126 ms 2040 KB Output is correct
8 Correct 195 ms 11124 KB Output is correct
9 Incorrect 1018 ms 28816 KB Output isn't correct
10 Incorrect 320 ms 1860 KB Output isn't correct
11 Correct 509 ms 4056 KB Output is correct
12 Correct 958 ms 23288 KB Output is correct
13 Correct 549 ms 28628 KB Output is correct