oj.uz

Submission #65494

# Submission time Handle Problem Language Result Execution time Memory
65494 2018-08-07T18:31:41 Z naderjemel Cake (CEOI14_cake) C++14
0 / 100
 1495 ms 11764 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); 
				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;
			for(int I=0;I<j-1;I++){
				pair<int,int> k = pq.top();
				pq.pop();
				update(1,0,n-1,k.second,maxi-I);
				qu.push_back({maxi-I,k.second});
			}
			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:97: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Incorrect 4 ms 360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 757 ms 6288 KB Output isn't correct
2 Correct 432 ms 6340 KB Output is correct
3 Correct 540 ms 6340 KB Output is correct
4 Correct 237 ms 6340 KB Output is correct
5 Incorrect 759 ms 6712 KB Output isn't correct
6 Incorrect 615 ms 10788 KB Output isn't correct
7 Correct 448 ms 10916 KB Output is correct
8 Correct 274 ms 10916 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 10916 KB Output is correct
2 Incorrect 283 ms 10916 KB Output isn't correct
3 Correct 254 ms 10916 KB Output is correct
4 Incorrect 3 ms 10916 KB Output isn't correct
5 Correct 298 ms 10916 KB Output is correct
6 Incorrect 399 ms 10916 KB Output isn't correct
7 Correct 314 ms 10916 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 10916 KB Output isn't correct
2 Correct 96 ms 10916 KB Output is correct
3 Correct 149 ms 10916 KB Output is correct
4 Incorrect 177 ms 10916 KB Output isn't correct
5 Incorrect 289 ms 10916 KB Output isn't correct
6 Correct 304 ms 10916 KB Output is correct
7 Correct 476 ms 10916 KB Output is correct
8 Correct 249 ms 10916 KB Output is correct
9 Incorrect 1495 ms 11764 KB Output isn't correct
10 Incorrect 970 ms 11764 KB Output isn't correct
11 Incorrect 1108 ms 11764 KB Output isn't correct
12 Correct 1330 ms 11764 KB Output is correct
13 Incorrect 1167 ms 11764 KB Output isn't correct