oj.uz

답안 #29839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29839 2017-07-21T08:19:07 Z rondojim 케이크 (CEOI14_cake) C++14
100 / 100
 886 ms 17648 KB 
#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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Correct 0 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 9 ms 17648 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 17648 KB Output is correct
2 Correct 236 ms 17648 KB Output is correct
3 Correct 283 ms 17648 KB Output is correct
4 Correct 166 ms 17648 KB Output is correct
5 Correct 439 ms 17648 KB Output is correct
6 Correct 369 ms 17648 KB Output is correct
7 Correct 366 ms 17648 KB Output is correct
8 Correct 243 ms 17648 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 17648 KB Output is correct
2 Correct 113 ms 17648 KB Output is correct
3 Correct 113 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 216 ms 17648 KB Output is correct
6 Correct 236 ms 17648 KB Output is correct
7 Correct 166 ms 17648 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 17648 KB Output is correct
2 Correct 39 ms 17648 KB Output is correct
3 Correct 79 ms 17648 KB Output is correct
4 Correct 106 ms 17648 KB Output is correct
5 Correct 123 ms 17648 KB Output is correct
6 Correct 146 ms 17648 KB Output is correct
7 Correct 159 ms 17648 KB Output is correct
8 Correct 226 ms 17648 KB Output is correct
9 Correct 886 ms 17648 KB Output is correct
10 Correct 446 ms 17648 KB Output is correct
11 Correct 519 ms 17648 KB Output is correct
12 Correct 806 ms 17648 KB Output is correct
13 Correct 549 ms 17648 KB Output is correct