답안 #43423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43423 2018-03-15T23:43:33 Z Hassoony 케이크 (CEOI14_cake) C++14
0 / 100
1182 ms 6484 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 s,int e,int val){
	if(s>e)return 0;
	if(l>e||r<s)return 0;
	if(seg[node]<=val)return 0;
	int mid=(l+r)/2;
	if(l>=s&&r<=e){
		if(l==r)return r;
		if(seg[node*2+1]>val)return q1(node*2+1,mid+1,r,s,e,val);
		return q1(node*2,l,mid,s,e,val);
	}
	int ret=q1(node*2+1,mid+1,r,s,e,val);
	if(ret!=0)return ret;
	return q1(node*2,l,mid,s,e,val);
}
int q2(int node,int l,int r,int s,int e,int val){
	if(s>e)return n+1;
	if(l>e||r<s)return n+1;
	if(seg[node]<=val)return n+1;
	int mid=(l+r)/2;
	if(l>=s&&r<=e){
		if(l==r)return r;
		if(seg[node*2]>val)return q2(node*2,l,mid,s,e,val);
		return q2(node*2+1,mid+1,r,s,e,val);
	}
	int ret=q2(node*2,l,mid,s,e,val);
	if(ret!=n+1)return ret;
	return q2(node*2+1,mid+1,r,s,e,val);
}
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=q2(1,1,n,st+1,n,mn);
                int res=ans-x-1;
                cout<<res<<endl;
            }
            else{
                int mn=q(1,1,n,st+1,x);
                int ans=q1(1,1,n,1,st-1,mn);
                int res=x-ans-1;
                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:75: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:80:23: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[250090]' [-Wformat=]
         scanf("%s",&oo);s=oo;
                       ^
cake.cpp:89:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<v.size();i++){
                 ^
cake.cpp:69: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:71:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
cake.cpp:78:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
                   ^
cake.cpp:80: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:82: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:96:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x);
                           ^
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Incorrect 2 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 742 ms 608 KB Output is correct
2 Incorrect 724 ms 736 KB Output isn't correct
3 Incorrect 725 ms 772 KB Output isn't correct
4 Correct 645 ms 828 KB Output is correct
5 Incorrect 795 ms 1028 KB Output isn't correct
6 Incorrect 755 ms 1032 KB Output isn't correct
7 Incorrect 750 ms 1044 KB Output isn't correct
8 Correct 716 ms 1044 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 227 ms 2956 KB Output isn't correct
2 Incorrect 218 ms 2956 KB Output isn't correct
3 Incorrect 230 ms 2956 KB Output isn't correct
4 Correct 2 ms 2956 KB Output is correct
5 Incorrect 270 ms 4560 KB Output isn't correct
6 Incorrect 254 ms 4596 KB Output isn't correct
7 Correct 231 ms 4596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 4596 KB Output isn't correct
2 Incorrect 87 ms 4596 KB Output isn't correct
3 Incorrect 159 ms 4596 KB Output isn't correct
4 Incorrect 159 ms 4596 KB Output isn't correct
5 Incorrect 243 ms 4596 KB Output isn't correct
6 Incorrect 305 ms 4596 KB Output isn't correct
7 Incorrect 342 ms 4596 KB Output isn't correct
8 Incorrect 378 ms 4596 KB Output isn't correct
9 Incorrect 1154 ms 6376 KB Output isn't correct
10 Incorrect 836 ms 6376 KB Output isn't correct
11 Incorrect 927 ms 6376 KB Output isn't correct
12 Incorrect 1182 ms 6376 KB Output isn't correct
13 Incorrect 1059 ms 6484 KB Output isn't correct