oj.uz

답안 #250228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250228 2020-07-17T08:56:36 Z errorgorn 케이크 (CEOI14_cake) C++14
100 / 100
 939 ms 32956 KB 
#include <cstdio>
#include <vector>
#include <set>
#include <utility>
using namespace std;
typedef pair<int,int> ii;

struct hull{
    set<ii> s;
    
    inline bool bad(set<ii>::iterator it){
        if (it==--s.end()) return false;
        else return (*next(it)).second<=(*it).second;
    }
    
    inline void add(ii i){
        auto it=s.insert(i).first;
        if (bad(it)){
            s.erase(it);
            return;
        }
        
        while (it!=s.begin() && bad(prev(it))){
            s.erase(prev(it));
        }
    }
    
    inline int query(int i){
        return (*s.lower_bound(ii(i,-1))).second;
    }
}left=*new hull(),right=*new hull();

struct node{
    int s,e,m;
    int val=0;
    node *l,*r;
    
    node (int _s,int _e){
        s=_s,e=_e,m=s+e>>1;
        
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    
    void update(int i,int j){
        if (s==e) val=j;
        else{
            if (i<=m) l->update(i,j);
            else r->update(i,j);
            val=max(l->val,r->val);
        }
    }
    
    int query(int i,int j){
        if (s==i && e==j) return val;
        else if (j<=m) return l->query(i,j);
        else if (m<i) return r->query(i,j);
        else return max(l->query(i,m),r->query(m+1,j));
    }
}*root=new node(0,250005);
const int INF=1000000000;

int n,k,q;
int arr[250005];
vector<int> top;

int __w;

void print(){
    for (auto &it:top) printf("%d ",it);
    printf("\n");
    
    for (auto &it:left.s) printf("%d-%d ",it.first,it.second);
    printf("\n");
    
    for (auto &it:right.s) printf("%d-%d ",it.first,it.second);
    printf("\n");
}

void change(int i,int j){
    arr[i]=j;
    root->update(i,j);
    if (i<k) left.add(ii(arr[i],k-i));
    else if (k<i) right.add(ii(arr[i],i-k));
}

int main(){
    scanf("%d%d",&n,&k);
    
    top.resize(10,0);
    __w=n+1;
    for (int x=1;x<=n;x++){
        scanf("%d",&arr[x]);
        if (n-arr[x]<10) top[n-arr[x]]=x;
        root->update(x,arr[x]);
    }
    
    for (int x=k-1;x;x--) left.add(ii(arr[x],k-x));
    left.add(ii(INF,k));
    
    for (int x=k+1;x<=n;x++) right.add(ii(arr[x],x-k));
    right.add(ii(INF,n+1-k));
    
    scanf("%d",&q);
    int a,b;
    while (q--){
        getchar();
        if (getchar()=='E'){
            scanf("%d%d",&a,&b);
            b--;
            for (int x=0;x<10;x++){
                if (top[x]==a){
                    top.erase(top.begin()+x);
                    break;
                }
            }
            
            top.insert(top.begin()+b,a);
            if (top.size()>10) top.pop_back();
            for (int x=b;~x;x--){
                change(top[x],__w++);
            }
            //print();
        }
        else{
            scanf("%d",&a);
            if (a==k){
                printf("0\n");
            }
            else if (a<k){
                printf("%d\n",k-a+right.query(root->query(a,k-1))-1);
            }
            else{
                printf("%d\n",a-k+left.query(root->query(k+1,a))-1);
            }
        }
    }
}

Compilation message

cake.cpp: In constructor 'node::node(int, int)':
cake.cpp:39:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~
cake.cpp: In function 'int main()':
cake.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
cake.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 28 ms 23808 KB Output is correct
5 Correct 38 ms 23936 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 574 ms 28280 KB Output is correct
2 Correct 291 ms 28280 KB Output is correct
3 Correct 408 ms 28280 KB Output is correct
4 Correct 237 ms 28280 KB Output is correct
5 Correct 598 ms 28544 KB Output is correct
6 Correct 437 ms 28920 KB Output is correct
7 Correct 429 ms 28804 KB Output is correct
8 Correct 253 ms 28920 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 26108 KB Output is correct
2 Correct 114 ms 25952 KB Output is correct
3 Correct 92 ms 25976 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 213 ms 27896 KB Output is correct
6 Correct 178 ms 27896 KB Output is correct
7 Correct 134 ms 27640 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 24312 KB Output is correct
2 Correct 67 ms 24440 KB Output is correct
3 Correct 103 ms 25080 KB Output is correct
4 Correct 141 ms 25204 KB Output is correct
5 Correct 190 ms 25300 KB Output is correct
6 Correct 195 ms 26144 KB Output is correct
7 Correct 182 ms 25976 KB Output is correct
8 Correct 266 ms 26884 KB Output is correct
9 Correct 939 ms 32760 KB Output is correct
10 Correct 562 ms 28664 KB Output is correct
11 Correct 654 ms 29612 KB Output is correct
12 Correct 922 ms 32248 KB Output is correct
13 Correct 684 ms 32956 KB Output is correct