oj.uz

Submission #65528

# Submission time Handle Problem Language Result Execution time Memory
65528 2018-08-07T20:59:07 Z naderjemel Cake (CEOI14_cake) C++14
100 / 100
 1359 ms 10656 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Correct 13 ms 596 KB Output is correct
5 Correct 25 ms 960 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 3200 KB Output is correct
2 Correct 436 ms 5072 KB Output is correct
3 Correct 529 ms 5176 KB Output is correct
4 Correct 241 ms 5176 KB Output is correct
5 Correct 708 ms 5652 KB Output is correct
6 Correct 649 ms 5652 KB Output is correct
7 Correct 502 ms 9912 KB Output is correct
8 Correct 248 ms 9912 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 9912 KB Output is correct
2 Correct 305 ms 9912 KB Output is correct
3 Correct 253 ms 9912 KB Output is correct
4 Correct 3 ms 9912 KB Output is correct
5 Correct 309 ms 9912 KB Output is correct
6 Correct 403 ms 9912 KB Output is correct
7 Correct 276 ms 9912 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 9912 KB Output is correct
2 Correct 90 ms 9912 KB Output is correct
3 Correct 166 ms 9912 KB Output is correct
4 Correct 173 ms 9912 KB Output is correct
5 Correct 324 ms 9912 KB Output is correct
6 Correct 337 ms 9912 KB Output is correct
7 Correct 415 ms 9912 KB Output is correct
8 Correct 295 ms 9912 KB Output is correct
9 Correct 1359 ms 10656 KB Output is correct
10 Correct 1113 ms 10656 KB Output is correct
11 Correct 1313 ms 10656 KB Output is correct
12 Correct 1356 ms 10656 KB Output is correct
13 Correct 1202 ms 10656 KB Output is correct