| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101626 |
2019-03-19T05:27:36 Z |
ShaneOng |
Cake (CEOI14_cake) |
C++14 |
|
1585 ms |
1049600 KB |
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n,st,q,arr[250009],flag;
struct node{
int s,e,m,v=0;
node *l,*r;
node(int a,int b){
s=a,e=b,m=(s+e)/2;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
v=max(l->v,r->v);
}else{
v=arr[s];
}
}
void up(int a,int b){
if(s==e&&s==a){
v=b;
return;
}
if(a<=m)
l->up(a,b);
else
r->up(a,b);
v=max(l->v,r->v);
}
int qu(int a,int b){
if(s==a&&b==e){
return v;
}
if(b<=m)
return l->qu(a,b);
if(a>m)
return r->qu(a,b);
return max(l->qu(a,m),r->qu(m+1,e));
}
int bs1(int a){
if(s==e)
return s+(v<a);
if(a>l->v)
return r->bs1(a);
return l->bs1(a);
}
int bs2(int a){
if(s==e)
return s-(v<a);
if(a>r->v)
return l->bs2(a);
return r->bs2(a);
}
}*root[2];
int main(){
scanf("%d%d",&n,&st);
priority_queue<ii,vector<ii>,greater<ii> > pq[2];
for(int x=0;x<n;x++){
scanf("%d",&arr[x]);
if(arr[x]>n-10)
pq[flag].push(ii(arr[x],x));
}
int ctr=n;
if(st>1)
root[0]=new node(0,st-2);
if(st<n)
root[1]=new node(st,n-1);
scanf("%d",&q);
for(int x=0,b,c;x<q;x++){
char a;
scanf(" %c",&a);
if(a=='E'){
scanf("%d%d",&b,&c);
while(!pq[flag].empty()){
ii temp=pq[flag].top();
pq[flag].pop();
if(temp.second==b-1)
continue;
if(temp.first>ctr-c+1){
temp.first++;
arr[temp.second]=temp.first;
if(temp.second+1>st){
root[1]->up(temp.second,temp.first);
}
if(temp.second+1<st)
root[0]->up(temp.second,temp.first);
}
pq[1-flag].push(temp);
}
if(b>st)
root[1]->up(b-1,ctr-c+2);
if(b<st)
root[0]->up(b-1,ctr-c+2);
pq[1-flag].push(ii(ctr-c+2,b-1));
arr[b-1]=ctr-c+2;
flag=1-flag;
while((int)pq[flag].size()>10)
pq[flag].pop();
ctr++;
if(st>1)
root[0]=new node(0,st-2);
if(st<n)
root[1]=new node(st,n-1);
assert((int)pq[flag].size()==min(10,n));
}else{
scanf("%d",&b);
if(b!=st){
if(b>st){
//printf("%d,%d\n",root[1]->qu(st,b-1),root[0]->bs2(root[1]->qu(st,b-1)));
int temp=-1;
if(st!=1)
temp=(root[0]->bs2(root[1]->qu(st,b-1)));
printf("%d\n",((b-1)-temp-1));
}
if(b<st){
//printf("%d,%d\n",root[0]->qu(b-1,st-2),root[1]->bs1(root[0]->qu(b-1,st-2)));
int temp=n;
if(st!=n)
temp=root[1]->bs1(root[0]->qu(b-1,st-2));
printf("%d\n",(temp-(b-1)-1));
}
}else
printf("0\n");
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&st);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&arr[x]);
~~~~~^~~~~~~~~~~~~~
cake.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
cake.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&a);
~~~~~^~~~~~~~~~
cake.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&b,&c);
~~~~~^~~~~~~~~~~~~~
cake.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&b);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1384 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
1485 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
1354 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
1340 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
1560 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
1429 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
1497 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
1551 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1311 ms |
893836 KB |
Output isn't correct |
| 2 |
Incorrect |
1253 ms |
818644 KB |
Output isn't correct |
| 3 |
Incorrect |
1258 ms |
799812 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Runtime error |
1469 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
1441 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
1585 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1479 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
1583 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
1456 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
1374 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
1329 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
1377 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
1327 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
1299 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
1421 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
1559 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
1508 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
1455 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
1564 ms |
1049600 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
