| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101807 |
2019-03-20T10:58:08 Z |
rocketninja7 |
Cake (CEOI14_cake) |
C++14 |
|
957 ms |
28516 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 index, int val){
if(s==e){
v=val;
}
else{
if(index<=m){
l->update(index, val);
}
else{
r->update(index, val);
}
v=max(l->v, r->v);
}
}
int query(int si, int ei){
if(si==s&&ei==e){
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 query2(int val, int dir){
if(s==e){
return s;
}
if(dir==1){
if(l->v<val){
return r->query2(val, dir);
}
return l->query2(val, dir);
}
if(r->v<val){
return l->query2(val, dir);
}
return r->query2(val, dir);
}
};
int main(){
int N, a;
scanf("%d%d", &N, &a);
int d[N+1];
vector<pair<int, int> > best;
node *lst=new node(0, a-1);
node *rst=new node(a+1, N+1);
for(int i=1;i<N+1;i++){
scanf("%d", &d[i]);
best.push_back(make_pair(-d[i], i));
if(i<a){
lst->update(i, d[i]);
}
else{
rst->update(i, d[i]);
}
}
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;
}
e--;
for(int j=0;j<best.size();j++){
if(best[j].first==-d[i]){
best.erase(best.begin()+j);
break;
}
}
for(int j=0;j<e;j++){
if(best[j].second<a){
lst->update(best[j].second, -(--best[j].first));
}
else if(best[j].second>a){
rst->update(best[j].second, -(--best[j].first));
}
else{
--best[j].first;
}
d[best[j].second]++;
}
d[i]=(e>0?d[best[e-1].second]-1:d[best[e].second]+1);
best.insert(best.begin()+e, make_pair(-d[i], i));
if(best.size()>10){
best.pop_back();
}
if(i<a){
lst->update(i, d[i]);
}
else if(i>a){
rst->update(i, d[i]);
}
}
else{
int b;
scanf("%d", &b);
if(b<a){
printf("%d\n", rst->query2(lst->query(b, a-1), 1)-1-b);
}
else if(b>a){
printf("%d\n", b-1-lst->query2(rst->query(a+1, b), -1));
}
else{
printf("0\n");
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:91:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<best.size();j++){
~^~~~~~~~~~~~
cake.cpp:60: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:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &d[i]);
~~~~~^~~~~~~~~~~~~
cake.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
cake.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c", &op);
~~~~~^~~~~~~~~~~~~
cake.cpp:86: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:123: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 |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| 5 |
Correct |
19 ms |
1536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
319 ms |
1372 KB |
Output is correct |
| 2 |
Correct |
167 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
246 ms |
1560 KB |
Output is correct |
| 4 |
Correct |
162 ms |
1536 KB |
Output is correct |
| 5 |
Correct |
367 ms |
3148 KB |
Output is correct |
| 6 |
Correct |
293 ms |
3072 KB |
Output is correct |
| 7 |
Correct |
278 ms |
3200 KB |
Output is correct |
| 8 |
Correct |
173 ms |
3072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
11628 KB |
Output is correct |
| 2 |
Correct |
115 ms |
11516 KB |
Output is correct |
| 3 |
Correct |
92 ms |
11468 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Correct |
230 ms |
27732 KB |
Output is correct |
| 6 |
Correct |
223 ms |
27544 KB |
Output is correct |
| 7 |
Correct |
159 ms |
27364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
768 KB |
Output is correct |
| 2 |
Correct |
31 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
109 ms |
5888 KB |
Output is correct |
| 4 |
Correct |
107 ms |
6080 KB |
Output is correct |
| 5 |
Correct |
110 ms |
860 KB |
Output is correct |
| 6 |
Correct |
177 ms |
8044 KB |
Output is correct |
| 7 |
Correct |
134 ms |
2056 KB |
Output is correct |
| 8 |
Correct |
180 ms |
11128 KB |
Output is correct |
| 9 |
Correct |
888 ms |
28508 KB |
Output is correct |
| 10 |
Correct |
269 ms |
1656 KB |
Output is correct |
| 11 |
Correct |
555 ms |
4056 KB |
Output is correct |
| 12 |
Correct |
957 ms |
23328 KB |
Output is correct |
| 13 |
Correct |
603 ms |
28516 KB |
Output is correct |
