Submission #65528

#	Time	Username	Problem	Language	Result	Execution time	Memory
65528		naderjemel	Cake (CEOI14_cake)	C++14	100 / 100	1359 ms	10656 KiB

cake

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,st;
int val,idx,maxi;
bool done;
int ns[250000];
int pos[250000];
vector<int> seg;
void init(){
	int s=1;
	for(;s<n;s<<=1); s<<=1;
	seg.assign(s,0);
}
int query(int p, int lo ,int hi, int l, int r){
	if(lo>=l && hi<=r) return seg[p];
	if(hi<l || lo>r) return 0;
	int mid=(lo+hi)/2;
	int x=query(p*2,lo,mid,l,r);
	int y=query(p*2+1,mid+1,hi,l,r);
	return max(x,y);
}
void build(int p, int lo, int hi){
	if(lo==hi){
		seg[p]=(ll)ns[lo];
		pos[lo]=p;
		return;
	}
	int mid=(lo+hi)/2;
	build(p*2,lo,mid);
	build(p*2+1,mid+1,hi);
	seg[p]=max(seg[p*2],seg[p*2+1]);
}
void update(int p, int lo, int hi, int dx, int va){
	if(lo==hi){
		if(lo==dx) seg[p]=va;
		return;
	}
	int mid=(lo+hi)/2;
	if(dx<=mid) update(p*2,lo,mid,dx,va);
	else update(p*2+1,mid+1,hi,dx,va);
	seg[p]=max(seg[p*2],seg[p*2+1]);
}
void le(int p ,int lo, int hi){
	if(seg[p]<val) return;
	if(hi<=st) return;
	if(lo==hi && !done){
		done=true;
		idx=lo;
		return;
	}
	int mid=(lo+hi)/2;
	le(p*2,lo,mid);
	if(done) return;
	le(p*2+1,mid+1,hi);
}
void ri(int p ,int lo, int hi){
	if(seg[p]<val) return;
	if(lo>=st) return;
	if(lo==hi && !done){
		done=true;
		idx=lo;
		return;
	}
	int mid=(lo+hi)/2;
	ri(p*2+1,mid+1,hi);
	if(done) return;
	ri(p*2,lo,mid);
}
int main(){
	scanf("%d%d",&n,&st); st--; maxi=n;
	priority_queue<pair<int,int> > pq;
	for(int i=0;i<n;i++){
		scanf("%d",&ns[i]);
		pq.push({ns[i],i});
	}
	int Q; scanf("%d",&Q); init(); build(1,0,n-1);
	while(Q--){
		char q; cin>>q; 
		if(q=='F'){done=false;
			int i; scanf("%d",&i); i--;
			if(i==st) printf("0\n");
			else if(i<st){
				val=query(1,0,n-1,i,st-1);
				le(1,0,n-1);
				if(!done) printf("%d\n", st-i+(n-st)-1);
				else printf("%d\n", (st-i)+(idx-st)-1);
			}
			else{
				val=query(1,0,n-1,st+1,i);
				ri(1,0,n-1); 
				//printf("%d %d\n", i,idx);
				if(done) printf("%d\n", i-st+(st-idx)-1);
				else printf("%d\n", (i-st)+st);
			}
		}
		else{
			int i,j; scanf("%d%d",&i,&j); i--; int cp=maxi+1; maxi+=j;
			vector<pair<int,int> > qu;
			vector<int> V;int I=0;
			while(I<j-1){ 
				pair<int,int> k = pq.top();
				//printf("hh%d\n", k.second);
				pq.pop();
				bool in=false;
				for(int l:V){
					if(l==k.second){
						in=true;
						break;
					}
				}
				if(in) continue;
				V.push_back(k.second);
				update(1,0,n-1,k.second,maxi-I);
				qu.push_back({maxi-I,k.second});
				I++;
			}
			for(pair<int,int> k:qu) pq.push(k);
			pq.push({cp,i});
			update(1,0,n-1,i,cp);
			//for(int i=0;i<n;i++) printf("%d ", seg[pos[i]]); printf("\n");
		}
	}
}

Compilation message (stderr)

cake.cpp: In function 'void init()':
cake.cpp:12:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(;s<n;s<<=1); s<<=1;
  ^~~
cake.cpp:12:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(;s<n;s<<=1); s<<=1;
                   ^
cake.cpp: In function 'int main()':
cake.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&st); st--; maxi=n;
  ~~~~~^~~~~~~~~~~~~~~
cake.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&ns[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d",&Q); init(); build(1,0,n-1);
         ~~~~~^~~~~~~~~
cake.cpp:81:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int i; scanf("%d",&i); i--;
           ~~~~~^~~~~~~~~
cake.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int i,j; scanf("%d%d",&i,&j); i--; int cp=maxi+1; maxi+=j;
             ~~~~~^~~~~~~~~~~~~~

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