| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250228 |
2020-07-17T08:56:36 Z |
errorgorn |
Cake (CEOI14_cake) |
C++14 |
|
939 ms |
32956 KB |
#include <cstdio>
#include <vector>
#include <set>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
struct hull{
set<ii> s;
inline bool bad(set<ii>::iterator it){
if (it==--s.end()) return false;
else return (*next(it)).second<=(*it).second;
}
inline void add(ii i){
auto it=s.insert(i).first;
if (bad(it)){
s.erase(it);
return;
}
while (it!=s.begin() && bad(prev(it))){
s.erase(prev(it));
}
}
inline int query(int i){
return (*s.lower_bound(ii(i,-1))).second;
}
}left=*new hull(),right=*new hull();
struct node{
int s,e,m;
int val=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int i,int j){
if (s==e) val=j;
else{
if (i<=m) l->update(i,j);
else r->update(i,j);
val=max(l->val,r->val);
}
}
int query(int i,int j){
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return max(l->query(i,m),r->query(m+1,j));
}
}*root=new node(0,250005);
const int INF=1000000000;
int n,k,q;
int arr[250005];
vector<int> top;
int __w;
void print(){
for (auto &it:top) printf("%d ",it);
printf("\n");
for (auto &it:left.s) printf("%d-%d ",it.first,it.second);
printf("\n");
for (auto &it:right.s) printf("%d-%d ",it.first,it.second);
printf("\n");
}
void change(int i,int j){
arr[i]=j;
root->update(i,j);
if (i<k) left.add(ii(arr[i],k-i));
else if (k<i) right.add(ii(arr[i],i-k));
}
int main(){
scanf("%d%d",&n,&k);
top.resize(10,0);
__w=n+1;
for (int x=1;x<=n;x++){
scanf("%d",&arr[x]);
if (n-arr[x]<10) top[n-arr[x]]=x;
root->update(x,arr[x]);
}
for (int x=k-1;x;x--) left.add(ii(arr[x],k-x));
left.add(ii(INF,k));
for (int x=k+1;x<=n;x++) right.add(ii(arr[x],x-k));
right.add(ii(INF,n+1-k));
scanf("%d",&q);
int a,b;
while (q--){
getchar();
if (getchar()=='E'){
scanf("%d%d",&a,&b);
b--;
for (int x=0;x<10;x++){
if (top[x]==a){
top.erase(top.begin()+x);
break;
}
}
top.insert(top.begin()+b,a);
if (top.size()>10) top.pop_back();
for (int x=b;~x;x--){
change(top[x],__w++);
}
//print();
}
else{
scanf("%d",&a);
if (a==k){
printf("0\n");
}
else if (a<k){
printf("%d\n",k-a+right.query(root->query(a,k-1))-1);
}
else{
printf("%d\n",a-k+left.query(root->query(k+1,a))-1);
}
}
}
}
Compilation message
cake.cpp: In constructor 'node::node(int, int)':
cake.cpp:39:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
s=_s,e=_e,m=s+e>>1;
~^~
cake.cpp: In function 'int main()':
cake.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
cake.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&arr[x]);
~~~~~^~~~~~~~~~~~~~
cake.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
cake.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
cake.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
28 ms |
23808 KB |
Output is correct |
| 5 |
Correct |
38 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
574 ms |
28280 KB |
Output is correct |
| 2 |
Correct |
291 ms |
28280 KB |
Output is correct |
| 3 |
Correct |
408 ms |
28280 KB |
Output is correct |
| 4 |
Correct |
237 ms |
28280 KB |
Output is correct |
| 5 |
Correct |
598 ms |
28544 KB |
Output is correct |
| 6 |
Correct |
437 ms |
28920 KB |
Output is correct |
| 7 |
Correct |
429 ms |
28804 KB |
Output is correct |
| 8 |
Correct |
253 ms |
28920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
26108 KB |
Output is correct |
| 2 |
Correct |
114 ms |
25952 KB |
Output is correct |
| 3 |
Correct |
92 ms |
25976 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
213 ms |
27896 KB |
Output is correct |
| 6 |
Correct |
178 ms |
27896 KB |
Output is correct |
| 7 |
Correct |
134 ms |
27640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
24312 KB |
Output is correct |
| 2 |
Correct |
67 ms |
24440 KB |
Output is correct |
| 3 |
Correct |
103 ms |
25080 KB |
Output is correct |
| 4 |
Correct |
141 ms |
25204 KB |
Output is correct |
| 5 |
Correct |
190 ms |
25300 KB |
Output is correct |
| 6 |
Correct |
195 ms |
26144 KB |
Output is correct |
| 7 |
Correct |
182 ms |
25976 KB |
Output is correct |
| 8 |
Correct |
266 ms |
26884 KB |
Output is correct |
| 9 |
Correct |
939 ms |
32760 KB |
Output is correct |
| 10 |
Correct |
562 ms |
28664 KB |
Output is correct |
| 11 |
Correct |
654 ms |
29612 KB |
Output is correct |
| 12 |
Correct |
922 ms |
32248 KB |
Output is correct |
| 13 |
Correct |
684 ms |
32956 KB |
Output is correct |
