답안 #43414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43414 2018-03-15T22:06:01 Z Hassoony 케이크 (CEOI14_cake) C++14
0 / 100
239 ms 33012 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);
        }
        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;
        //        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:88: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 4 ms 1124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 1628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 1752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 229 ms 6172 KB Output isn't correct
5 Runtime error 6 ms 6968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 10 ms 7348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 7716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 239 ms 12724 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 42 ms 15820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 46 ms 16572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 111 ms 17824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 1 ms 17824 KB Output isn't correct
5 Execution timed out 31 ms 18476 KB Time limit exceeded (wall clock)
6 Runtime error 93 ms 20764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 237 ms 24028 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 24028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 24028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 24028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 9 ms 24028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 24028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 24080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 24080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 18 ms 26352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 79 ms 29044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 2 ms 29044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 5 ms 29044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 36 ms 32636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 77 ms 33012 KB Execution killed with signal 11 (could be triggered by violating memory limits)