Submission #29839

#	Time	Username	Problem	Language	Result	Execution time	Memory
29839		rondojim	Cake (CEOI14_cake)	C++14	100 / 100	886 ms	17648 KiB

cake

#include "bits/stdc++.h"
#define MAXN 500009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
#define left cep
#define right sag
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,a,arr[MAXN],p[MAXN],s[MAXN<<2],F[MAXN*2];
void update(int p,int v,int nd,int x,int y){
	if(x==y){
		s[nd]=v;
		return;
	}
	int mid=(x+y)>>1;
	if(p<=mid)
		update(p,v,nd<<1,x,mid);
	else	
		update(p,v,nd<<1|1,mid+1,y);
	s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
int tap(int l,int r,int nd,int x,int y){
	if(l>y or x>r)
		return INF;
	if(l<=x and y<=r)
		return s[nd];
	int mid=(x+y)>>1;	
	return min(tap(l,r,nd<<1,x,mid),tap(l,r,nd<<1|1,mid+1,y));	
}
int left(int l,int r,int v,int nd,int x,int y){
	if(l>y or x>r or s[nd]>v)
		return -1;
	if(x==y)
		return x;
	int mid=(x+y)>>1;
	int ii=left(l,r,v,nd<<1,x,mid);
	if(~ii)
		return ii;
	return left(l,r,v,nd<<1|1,mid+1,y);	
}
int right(int l,int r,int v,int nd,int x,int y){
	if(l>y or x>r or s[nd]>v)
		return -1;
	if(x==y)
		return x;
	int mid=(x+y)>>1;
	int ii=right(l,r,v,nd<<1|1,mid+1,y);
	if(~ii)
		return ii;
	return right(l,r,v,nd<<1,x,mid);	
}
void change(int x,int val){
	x+=MAXN;
	for(;x<MAXN*2;x+=x&(-x))
		F[x]+=val;
}
void upd(int p,int x){
	change(arr[p],-1);
	change(x,+1);
	arr[p]=x;
	update(p,x,1,1,n);
}
int get(int x){x+=MAXN;
	int res=0;
	for(;x;x-=x&(-x))
		res+=F[x];
	return res;	
}
int main(){
	//~ #ifndef ONLINE_JUDGE
    //~ freopen("file.in", "r", stdin);
    //~ freopen("file.out", "w", stdout);
	//~ #endif
	scanf("%d%d",&n,&a);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		p[n-x+1]=i;arr[i]=n-x+1;
		change(n-x+1,+1);
		update(i,n-x+1,1,1,n);
	}
	int q;
	scanf("%d",&q);
	while(q--){
		char c;
		scanf(" %c",&c);
		if(c=='F'){
			int x;
			scanf("%d",&x);
			if(x==a){
				puts("0");
				continue;
			}
			if(x<a){
				int mx=tap(x,a-1,1,1,n);
				int pos=left(a+1,n,mx,1,1,n);
				if(pos==-1)
					printf("%d\n",n-x);
				else
					printf("%d\n",pos-x-1);
			}
			else{
				int mx=tap(a+1,x,1,1,n);
				int pos=right(1,a-1,mx,1,1,n);
				if(pos==-1)
					printf("%d\n",x-1);	
				else
					printf("%d\n",x-pos-1);
			}
		}
		else{
			int x,y;
			scanf("%d%d",&x,&y);
			//~ printf("E %d %d\n",x,y);
			int rank=get(arr[x]);
			//~ debug(rank);	
			//~ debug(y);	
			if(rank==y)
				continue;	
			if(y<rank){
				int val=arr[p[y]];
				upd(x,--val);
				for(int i=y-1;i>=1;i--)
					upd(p[i],--val);
				for(int i=min(10,rank);i>y;i--)
					p[i]=p[i-1];
				p[y]=x;	
			}	
			else{
				int val=arr[p[y]];
				assert(p[rank]==x);
				for(int i=rank;i<y;i++)
					p[i]=p[i+1];
				p[y]=x;	
				for(int i=y;i>=rank;i--)
					upd(p[i],val--);
			}
			//~ for(int i=1;i<=n;i++)
				//~ cout<<arr[i]<<" ";
			//~ cout<<endl;
			//~ for(int i=1;i<=n;i++)
				//~ cout<<p[i]<<" ";
			//~ cout<<endl;	
		}
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&a);
                     ^
cake.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^
cake.cpp:96:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
cake.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
cake.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
                  ^
cake.cpp:126:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&x,&y);
                       ^

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50