oj.uz

답안 #101854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101854 2019-03-20T14:33:08 Z ShaneOng 케이크 (CEOI14_cake) C++14
100 / 100
 1004 ms 26540 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,st,q,arr[250009],flag;
priority_queue<ii,vector<ii>,greater<ii> > pq[2];
struct node{
    int s,e,m,v=0;
    node *l,*r;
    node(int a,int b){
        s=a,e=b,m=(s+e)/2;
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
            v=max(l->v,r->v);
        }else{
            v=arr[s];
        }

    }
    void up(int a,int b){
        if(s==e&&s==a){
            v=b;
            return;
        }
        if(a<=m)
            l->up(a,b);
        else
            r->up(a,b);

        v=max(l->v,r->v);
    }
    int qu(int a,int b){
        if(s==a&&b==e){
            return v;
        }
        if(b<=m)
            return l->qu(a,b);
        if(a>m)
            return r->qu(a,b);
        return max(l->qu(a,m),r->qu(m+1,b));
    }
    int bs1(int a){
        if(s==e)
            return s+(v<a);
        if(a>l->v)
            return r->bs1(a);
        return l->bs1(a);
    }
    int bs2(int a){
        if(s==e)
            return s-(v<a);
        if(a>r->v)
            return l->bs2(a);
        return r->bs2(a);
    }
}*root[2];
int main(){
    //freopen("temp.txt","w",stdout);
    scanf("%d%d",&n,&st);

    for(int x=0;x<n;x++){
        scanf("%d",&arr[x]);
        if(arr[x]>n-10)
            pq[flag].push(ii(arr[x],x));
    }
    int ctr=n;
    if(st>1)
        root[0]=new node(0,st-2);
    if(st<n)
        root[1]=new node(st,n-1);

    scanf("%d",&q);
    for(int x=0,b,c;x<q;x++){
        char a;
        scanf(" %c",&a);

        if(a=='E'){
            scanf("%d%d",&b,&c);
            int newnum=ctr+1;
            while(!pq[flag].empty()){
                ii temp=pq[flag].top();
                pq[flag].pop();
                if(temp.second==b-1)
                    continue;
                if((int)pq[flag].size()<=c-2){
                    if((int)pq[flag].size()==c-2)
                        newnum=temp.first;
                    temp.first++;
                    if(temp.second+1>st){
                        root[1]->up(temp.second,temp.first);
                    }
                    if(temp.second+1<st)
                        root[0]->up(temp.second,temp.first);
                    arr[temp.second]=temp.first;
                }
                pq[1-flag].push(temp);
            }
            if(b>st)
                root[1]->up(b-1,newnum);
            if(b<st)
                root[0]->up(b-1,newnum);
            pq[1-flag].push(ii(newnum,b-1));
            arr[b-1]=newnum;
            flag=1-flag;
            while((int)pq[flag].size()>10)
                pq[flag].pop();
            ctr++;
            assert((int)pq[flag].size()==min(10,n));
        }else{
            /*for(int x=0;x<n;x++){
                printf("%d ",arr[x]);
            }
            printf("\n");*/

            scanf("%d",&b);
            if(b!=st){
               // printf("%d,%d:",x,b);
                if(b>st){
                    //printf("%d,%d\n",root[1]->qu(st,b-1),root[0]->bs2(root[1]->qu(st,b-1)));
                    int temp=-1;
                    if(st!=1)
                        temp=(root[0]->bs2(root[1]->qu(st,b-1)));
                    printf("%d\n",((b-1)-temp-1));
                }
                if(b<st){
                    //printf("%d,%d\n",root[0]->qu(b-1,st-2),root[1]->bs1(root[0]->qu(b-1,st-2)));
                    int temp=n;
                    if(st!=n)
                        temp=root[1]->bs1(root[0]->qu(b-1,st-2));
                    printf("%d\n",(temp-(b-1)-1));
                }
            }else
                printf("0\n");
        }
    }


}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&st);
     ~~~~~^~~~~~~~~~~~~~~
cake.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&a);
         ~~~~~^~~~~~~~~~
cake.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&b,&c);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 17 ms 1408 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 1280 KB Output is correct
2 Correct 290 ms 1280 KB Output is correct
3 Correct 357 ms 1280 KB Output is correct
4 Correct 295 ms 1280 KB Output is correct
5 Correct 435 ms 2812 KB Output is correct
6 Correct 444 ms 2936 KB Output is correct
7 Correct 358 ms 2820 KB Output is correct
8 Correct 275 ms 2816 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 10748 KB Output is correct
2 Correct 90 ms 10616 KB Output is correct
3 Correct 70 ms 10616 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 235 ms 25464 KB Output is correct
6 Correct 163 ms 25464 KB Output is correct
7 Correct 98 ms 25208 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 768 KB Output is correct
2 Correct 43 ms 964 KB Output is correct
3 Correct 95 ms 5496 KB Output is correct
4 Correct 110 ms 5496 KB Output is correct
5 Correct 124 ms 896 KB Output is correct
6 Correct 201 ms 7244 KB Output is correct
7 Correct 140 ms 1784 KB Output is correct
8 Correct 224 ms 10280 KB Output is correct
9 Correct 928 ms 26428 KB Output is correct
10 Correct 395 ms 1840 KB Output is correct
11 Correct 569 ms 3624 KB Output is correct
12 Correct 1004 ms 21528 KB Output is correct
13 Correct 613 ms 26540 KB Output is correct