oj.uz

Submission #26344

# Submission time Handle Problem Language Result Execution time Memory
26344 2017-06-29T09:00:24 Z Kerim Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 29324 KB 
#include "bits/stdc++.h"
#include<ext/pb_ds/assoc_container.hpp>
#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;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int,int> PII;
typedef tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> tes;
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];
tes st;
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 upd(int p,int x){
	st.erase(mp(arr[p],p));
	arr[p]=x;update(p,x,1,1,n);
	st.insert(mp(x,p));
}
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;
		st.insert(mp(n-x+1,i));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=st.order_of_key(mp(arr[x],-1))+1;
			//~ 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:79: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:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^
cake.cpp:87:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
                ^
cake.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
cake.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
                  ^
cake.cpp:117: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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13748 KB Output is correct
2 Correct 0 ms 13748 KB Output is correct
3 Correct 0 ms 13748 KB Output is correct
4 Correct 9 ms 13880 KB Output is correct
5 Correct 33 ms 14408 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1146 ms 14276 KB Output is correct
2 Correct 689 ms 14408 KB Output is correct
3 Correct 799 ms 14408 KB Output is correct
4 Correct 609 ms 14408 KB Output is correct
5 Correct 1293 ms 15332 KB Output is correct
6 Correct 1099 ms 15332 KB Output is correct
7 Correct 866 ms 15332 KB Output is correct
8 Correct 809 ms 15332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 19952 KB Output is correct
2 Correct 176 ms 19952 KB Output is correct
3 Correct 159 ms 19952 KB Output is correct
4 Correct 0 ms 13748 KB Output is correct
5 Correct 476 ms 29324 KB Output is correct
6 Correct 476 ms 29324 KB Output is correct
7 Correct 356 ms 29324 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 14012 KB Output is correct
2 Correct 83 ms 14012 KB Output is correct
3 Correct 196 ms 16916 KB Output is correct
4 Correct 286 ms 16916 KB Output is correct
5 Correct 316 ms 13880 KB Output is correct
6 Correct 379 ms 17840 KB Output is correct
7 Correct 303 ms 14408 KB Output is correct
8 Correct 579 ms 19952 KB Output is correct
9 Execution timed out 2000 ms 29324 KB Execution timed out
10 Correct 896 ms 13880 KB Output is correct
11 Correct 1326 ms 15068 KB Output is correct
12 Execution timed out 2000 ms 26288 KB Execution timed out
13 Correct 1723 ms 29324 KB Output is correct