| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65527 |
2018-08-07T20:57:23 Z |
naderjemel |
Cake (CEOI14_cake) |
C++14 |
|
1278 ms |
10564 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("p%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;
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
675 ms |
2648 KB |
Output isn't correct |
| 2 |
Incorrect |
446 ms |
4892 KB |
Output isn't correct |
| 3 |
Incorrect |
517 ms |
4892 KB |
Output isn't correct |
| 4 |
Incorrect |
288 ms |
4892 KB |
Output isn't correct |
| 5 |
Incorrect |
816 ms |
5520 KB |
Output isn't correct |
| 6 |
Incorrect |
634 ms |
5520 KB |
Output isn't correct |
| 7 |
Incorrect |
487 ms |
9440 KB |
Output isn't correct |
| 8 |
Incorrect |
234 ms |
9440 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
9440 KB |
Output isn't correct |
| 2 |
Incorrect |
238 ms |
9440 KB |
Output isn't correct |
| 3 |
Incorrect |
239 ms |
9440 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
9440 KB |
Output is correct |
| 5 |
Incorrect |
282 ms |
9440 KB |
Output isn't correct |
| 6 |
Incorrect |
281 ms |
9440 KB |
Output isn't correct |
| 7 |
Incorrect |
254 ms |
9440 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
9440 KB |
Output isn't correct |
| 2 |
Incorrect |
91 ms |
9440 KB |
Output isn't correct |
| 3 |
Incorrect |
161 ms |
9440 KB |
Output isn't correct |
| 4 |
Incorrect |
219 ms |
9440 KB |
Output isn't correct |
| 5 |
Incorrect |
351 ms |
9440 KB |
Output isn't correct |
| 6 |
Incorrect |
320 ms |
9440 KB |
Output isn't correct |
| 7 |
Incorrect |
372 ms |
9440 KB |
Output isn't correct |
| 8 |
Incorrect |
262 ms |
9440 KB |
Output isn't correct |
| 9 |
Incorrect |
1278 ms |
10564 KB |
Output isn't correct |
| 10 |
Incorrect |
1002 ms |
10564 KB |
Output isn't correct |
| 11 |
Incorrect |
1124 ms |
10564 KB |
Output isn't correct |
| 12 |
Incorrect |
1248 ms |
10564 KB |
Output isn't correct |
| 13 |
Incorrect |
1148 ms |
10564 KB |
Output isn't correct |
