| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101612 |
2019-03-19T05:14:43 Z |
rocketninja7 |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
54496 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int s, e, m, v;
node *l, *r;
node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), v(0){
if(s<e){
l=new node(s, m);
r=new node(m+1, e);
}
}
void update(int i, int val){
if(s==i&&e==i){
v=val;
}
else{
if(i<=m){
l->update(i, val);
}
else{
r->update(i, val);
}
v=max(l->v, r->v);
}
}
int query(int si, int ei){
if(s==si&&e==ei){
return v;
}
if(ei<=m){
return l->query(si, ei);
}
if(si>m){
return r->query(si, ei);
}
return max(l->query(si, m), r->query(m+1, ei));
}
};
int main(){
int N, a;
scanf("%d%d", &N, &a);
node *root=new node(1, N-1);
int d[N+1];
vector<pair<int, int> > best;
for(int i=1;i<N+1;i++){
scanf("%d", &d[(i+N-1-a)%N+1]);
best.push_back(make_pair(-d[(i+N-1-a)%N+1], (i+N-1-a)%N+1));
if(i==a){
continue;
}
root->update((i+N-1-a)%N+1, d[(i+N-1-a)%N+1]);
}
sort(best.begin(), best.end());
while(best.size()>10){
best.pop_back();
}
int Q;
scanf("%d", &Q);
while(Q--){
char op;
scanf("\n%c", &op);
if(op=='E'){
int i, e;
scanf("%d%d", &i, &e);
if(N==1){
continue;
}
int tempE=e;
i=(i+N-1-a)%N+1;
e--;
for(int j=0;j<best.size();j++){
if(best[j].second==i){
best.erase(best.begin()+j);
}
}
int j=0;
while(e--){
--best[j].first;
root->update(best[j].second, ++d[best[j].second]);
j++;
}
if(tempE>1){
d[i]=d[best[j-1].second]-1;
}
else{
d[i]=d[best[j].second]+1;
}
root->update(i, d[i]);
best.insert(best.begin()+tempE-1, make_pair(-d[i], i));
if(best.size()>10){
best.erase(--best.end());
}
}
else{
int b;
scanf("%d", &b);
if(b==a){
printf("0\n");
continue;
}
b=(b+N-1-a)%N+1;
if(b==best[0].second){
printf("%d\n", N-1);
continue;
}
int left=root->query(1, b), right=root->query(b, N-1);
if(left<right){
int s=b, e=N;
while(s<e-1){
int m=(s+e)/2;
if(root->query(m, N-1)<left){
e=m;
}
else{
s=m;
}
}
printf("%d\n", b-1+N-s);
}
else{
int s=0, e=b;
while(s<e-1){
int m=(s+e)/2;
if(root->query(1, m)<right){
s=m;
}
else{
e=m;
}
}
printf("%d\n", s+N-b);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:75:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<best.size();j++){
~^~~~~~~~~~~~
cake.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &a);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d[(i+N-1-a)%N+1]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
cake.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c", &op);
~~~~~^~~~~~~~~~~~~
cake.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &i, &e);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:100: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 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
2680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
8 ms |
2816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
25 ms |
2816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Incorrect |
165 ms |
1560 KB |
Output isn't correct |
| 5 |
Runtime error |
23 ms |
5880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
18 ms |
5888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
162 ms |
6040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
209 ms |
3072 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
541 ms |
11688 KB |
Output isn't correct |
| 2 |
Runtime error |
72 ms |
21740 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
66 ms |
21780 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
629 ms |
27680 KB |
Output isn't correct |
| 6 |
Incorrect |
568 ms |
27624 KB |
Output isn't correct |
| 7 |
Runtime error |
160 ms |
53620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
10 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
50 ms |
11336 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
35 ms |
11252 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
4 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
252 ms |
14960 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
46 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
197 ms |
11120 KB |
Output isn't correct |
| 9 |
Runtime error |
1697 ms |
54496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
4 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
41 ms |
4980 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Execution timed out |
2037 ms |
23148 KB |
Time limit exceeded |
| 13 |
Incorrect |
1493 ms |
28584 KB |
Output isn't correct |
