답안 #43415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43415 2018-03-15T22:14:29 Z Hassoony 케이크 (CEOI14_cake) C++14
0 / 100
2000 ms 121064 KB
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MX=2e5+9;
int n,Q,st,a[MX],seg[MX*5],x,y;
vector<int>v;
string s;
char oo[MX];
void build(int node,int l,int r){
    if(l==r){
        seg[node]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    seg[node]=max(seg[node*2],seg[node*2+1]);
}
bool cmp(int x,int y){
    return a[x]>a[y];
}
void up(int node,int l,int r,int ind){
    if(l>ind||r<ind)return;
    if(l==r){
        seg[node]=a[l];
        return;
    }
    int mid=(l+r)/2;
    up(node*2,l,mid,ind);
    up(node*2+1,mid+1,r,ind);
    seg[node]=max(seg[node*2],seg[node*2+1]);
}
int q(int node,int l,int r,int s,int e){
    if(l>e||r<s)return 0;
    if(l>=s&&r<=e)return seg[node];
    int mid=(l+r)/2;
    return max(q(node*2,l,mid,s,e),q(node*2+1,mid+1,r,s,e));
}
int q1(int node,int l,int r,int ind,int mn){
    if(r<ind)return 0;
    if(l==r){
        if(a[l]>mn)return l;
        return 0;
    }
    int mid=(l+r)/2;
    if(mid<ind)return q1(node*2+1,mid+1,r,ind,mn);
    if(seg[node*2]<=mn)return q1(node*2+1,mid+1,r,ind,mn);
    else return q1(node*2,l,mid,ind,mn);
}
int q2(int node,int l,int r,int ind,int mn){
    if(l>ind)return 0;
    if(l==r){
        if(a[l]>mn)return l;
        return 0;
    }
    int mid=(l+r)/2;
    if(mid+1>ind)return q2(node*2,l,mid,ind,mn);
    if(seg[node*2+1]<=mn)return q2(node*2,l,mid,ind,mn);
    else return q2(node*2+1,mid+1,r,ind,mn);

}
int main(){
    scanf("%d%d",&n,&st);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>n-10)v.push_back(i);
    }
    sort(v.begin(),v.end(),cmp);
    build(1,1,n);
    scanf("%d",&Q);
    while(Q--){
        scanf("%s",&oo);s=oo;
        if(s=="E"){
            scanf("%d%d",&x,&y);
            a[x]=a[v[y-1]]+1;
            up(1,1,n,x);
            for(int i=0;i<y-1;i++){
                a[v[i]]++;
                up(1,1,n,v[i]);
            }
            int ok=0;
            for(auto pp:v)if(pp==x)ok=1;
            if(!ok)v.pop_back();
            sort(v.begin(),v.end(),cmp);
            for(int i=1;i<=n;i++)cout<<a[i]<<" ";
            cout<<endl;
        }
        else{
            scanf("%d",&x);
            if(x==st){
                puts("0");
                continue;
            }
            if(x<st){
                int mn=q(1,1,n,x,st-1);
                int ans=q1(1,1,n,st,mn);
                int res=ans-x-1;
        //        cout<<ans<<endl;
                if(ans==0)res=n-x;
                else if(ans<=st)res=st-x;
                cout<<res<<endl;
            }
            else{
                int mn=q(1,1,n,st+1,x);
                int ans=q2(1,1,n,st,mn);
                int res=x-ans-1;
      //          cout<<ans<<endl;
                if(ans==0)res=x-1;
                else if(ans>=st)res=x-st;
                cout<<res<<endl;
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:73:23: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[200009]' [-Wformat=]
         scanf("%s",&oo);s=oo;
                       ^
cake.cpp:64:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&st);
                         ^
cake.cpp:66:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
cake.cpp:71:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
                   ^
cake.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&oo);s=oo;
                        ^
cake.cpp:75:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&x,&y);
                                ^
cake.cpp:90:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
                           ^
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 1248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 362 ms 19268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 16 ms 19268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Execution timed out 2080 ms 108832 KB Time limit exceeded
5 Runtime error 47 ms 108832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 170 ms 108832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 33 ms 108832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Execution timed out 2078 ms 121064 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Runtime error 160 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 164 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 567 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 5 ms 121064 KB Output isn't correct
5 Execution timed out 30 ms 121064 KB Time limit exceeded (wall clock)
6 Runtime error 101 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 813 ms 121064 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 7 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 58 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 55 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 5 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 73 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 13 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 111 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 107 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 5 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 25 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 276 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 81 ms 121064 KB Execution killed with signal 11 (could be triggered by violating memory limits)