oj.uz

답안 #26347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26347 2017-06-29T09:05:35 Z Kerim 케이크 (CEOI14_cake) C++14
100 / 100
 863 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 3 ms 17648 KB Output is correct
5 Correct 19 ms 17648 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 409 ms 17648 KB Output is correct
2 Correct 349 ms 17648 KB Output is correct
3 Correct 306 ms 17648 KB Output is correct
4 Correct 193 ms 17648 KB Output is correct
5 Correct 479 ms 17648 KB Output is correct
6 Correct 396 ms 17648 KB Output is correct
7 Correct 356 ms 17648 KB Output is correct
8 Correct 183 ms 17648 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 17648 KB Output is correct
2 Correct 116 ms 17648 KB Output is correct
3 Correct 96 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 186 ms 17648 KB Output is correct
6 Correct 219 ms 17648 KB Output is correct
7 Correct 189 ms 17648 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 17648 KB Output is correct
2 Correct 36 ms 17648 KB Output is correct
3 Correct 113 ms 17648 KB Output is correct
4 Correct 106 ms 17648 KB Output is correct
5 Correct 149 ms 17648 KB Output is correct
6 Correct 163 ms 17648 KB Output is correct
7 Correct 169 ms 17648 KB Output is correct
8 Correct 203 ms 17648 KB Output is correct
9 Correct 829 ms 17648 KB Output is correct
10 Correct 453 ms 17648 KB Output is correct
11 Correct 579 ms 17648 KB Output is correct
12 Correct 863 ms 17648 KB Output is correct
13 Correct 689 ms 17648 KB Output is correct