답안 #43422

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

using namespace std;
typedef long long ll;
const int MX=250090;
int n,Q,st,a[MX],seg[MX*5],x,y,orig[MX];
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);
    for(int i=0;i<v.size();i++)orig[v[i]]=i;
    build(1,1,n);
    int val=n;
    scanf("%d",&Q);
    while(Q--){
        scanf("%s",&oo);s=oo;
        if(s=="E"){
            scanf("%d%d",&x,&y);
            int idx=orig[x];
			for(int x:v)orig[x]=-1;
			if(idx==-1)idx=v.size()-1;
			for(int i=idx;i>=y;i--)v[i]=v[i-1];
			v[y-1]=x;
			val+=11;
			for(int i=0;i<v.size();i++){
				orig[v[i]]=i;
				a[v[i]]=val-i;
				up(1,1,n,v[i]);
			}
        }
        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;
            }
        }
    }
}
/*
12 1
1 2 3 4 5 6 7 8 9 10 11 12
20
E 1 1
*/

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++)orig[v[i]]=i;
                  ^
cake.cpp:74:23: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[250090]' [-Wformat=]
         scanf("%s",&oo);s=oo;
                       ^
cake.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<v.size();i++){
                 ^
cake.cpp:63: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:65:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
cake.cpp:72:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
                   ^
cake.cpp:74: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:76: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 Incorrect 735 ms 608 KB Output isn't correct
2 Incorrect 673 ms 680 KB Output isn't correct
3 Incorrect 673 ms 716 KB Output isn't correct
4 Correct 658 ms 788 KB Output is correct
5 Incorrect 779 ms 932 KB Output isn't correct
6 Incorrect 716 ms 1060 KB Output isn't correct
7 Incorrect 751 ms 1060 KB Output isn't correct
8 Correct 749 ms 1060 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 246 ms 2960 KB Output isn't correct
2 Incorrect 218 ms 2960 KB Output isn't correct
3 Incorrect 207 ms 2960 KB Output isn't correct
4 Incorrect 1 ms 2960 KB Output isn't correct
5 Incorrect 248 ms 4732 KB Output isn't correct
6 Incorrect 289 ms 4732 KB Output isn't correct
7 Incorrect 229 ms 4732 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 4732 KB Output isn't correct
2 Incorrect 89 ms 4732 KB Output isn't correct
3 Incorrect 152 ms 4732 KB Output isn't correct
4 Incorrect 162 ms 4732 KB Output isn't correct
5 Incorrect 234 ms 4732 KB Output isn't correct
6 Incorrect 300 ms 4732 KB Output isn't correct
7 Incorrect 361 ms 4732 KB Output isn't correct
8 Incorrect 365 ms 4732 KB Output isn't correct
9 Incorrect 1207 ms 6372 KB Output isn't correct
10 Incorrect 834 ms 6372 KB Output isn't correct
11 Incorrect 891 ms 6372 KB Output isn't correct
12 Incorrect 1129 ms 6372 KB Output isn't correct
13 Incorrect 1051 ms 6392 KB Output isn't correct