| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 336799 |
2020-12-16T20:47:27 Z |
nafis_shifat |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
18668 KB |
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5e4+7;
const int inf=1e9;
struct segtree {
int tree[4*mxn];
int n;
void init(int N) {
n = N;
for(int i = 1; i <= 4 * n; i++) tree[i] = inf;
}
void update(int node,int b,int e,int p,int v) {
if(b > p || e < p) return;
if(b == e) {
tree[node] = v;
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
update(left,b,mid,p,v);
update(right,mid+1,e,p,v);
tree[node] = max(tree[left],tree[right]);
}
int queryL(int node,int b,int e,int p,int x) {
if(e < p) return n + 1;
if(tree[node] < x) return n + 1;
if(b == e) {
return b;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
if(b >= p) {
if(tree[left] >= x) return queryL(left,b,mid,p,x);
else return queryL(right,mid+1,e,p,x);
}
int v1 = queryL(left,b,mid,p,x);
if(v1 != n + 1) return v1;
return queryL(right,mid+1,e,p,x);
}
int queryR(int node,int b,int e,int p,int x) {
if(b > p) return 0;
if(tree[node] < x) return 0;
if(b == e) {
return b;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
if(e <= p) {
if(tree[right] >= x) return queryR(right,mid+1,e,p,x);
else return queryR(left,b,mid,p,x);
}
int v1 = queryR(right,mid+1,e,p,x);
if(v1 != 0) return v1;
return queryR(left,b,mid,p,x);
}
int query(int node,int b,int e,int l,int r) {
if(e < l || b > r) return 0;
if(b >= l && e <= r) {
return tree[node];
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
return max(query(left,b,mid,l,r),query(right,mid+1,e,l,r));
}
} seg;
int main() {
int n,a;
cin>>n>>a;
int d[n+1];
set<pii> st;
for(int i = 1; i <= n; i++) {
scanf("%d",&d[i]);
st.insert({d[i],i});
}
seg.init(n);
for(int i = 1; i <= n; i++) seg.update(1,1,n,i,d[i]);
int q;
cin>>q;
while(q--) {
char c;
cin>>c;
if(c == 'E') {
int x,e;
scanf("%d%d",&x,&e);
int v = 1;
auto it = st.rbegin();
stack<pii> s;
for(; v < e; it++, v++) {
s.push(*it);
}
int f = -1;
if(!s.empty()) {
f = s.top().first;
}
while(!s.empty()) {
pii t = s.top();
s.pop();
st.erase(t);
st.insert({t.first + 1,t.second});
d[t.second] = t.first + 1;
seg.update(1,1,n,t.second,d[t.second]);
}
if(f == -1) {
f = it->first + 1;
}
st.erase({d[x],x});
st.insert({f,x});
d[x] = f;
seg.update(1,1,n,x,d[x]);
} else {
int x;
scanf("%d",&x);
if(x == a) {
printf("0\n");
continue;
}
if(x < a) {
int v = seg.query(1,1,n,x,a-1);
int ind = seg.queryL(1,1,n,a+1,v);
int res = ind - 1 - a + a - x;
printf("%d\n",res);
} else {
int v = seg.query(1,1,n,a+1,x);
int ind = seg.queryR(1,1,n,a-1,v);
int res = a - ind - 1 + x - a;
printf("%d\n",res);
}
}
}
}
Compilation message
cake.cpp: In member function 'void segtree::update(int, int, int, int, int)':
cake.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | int mid=b+e>>1;
| ~^~
cake.cpp: In member function 'int segtree::queryL(int, int, int, int, int)':
cake.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid=b+e>>1;
| ~^~
cake.cpp: In member function 'int segtree::queryR(int, int, int, int, int)':
cake.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid=b+e>>1;
| ~^~
cake.cpp: In member function 'int segtree::query(int, int, int, int, int)':
cake.cpp:71:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid=b+e>>1;
| ~^~
cake.cpp: In function 'int main()':
cake.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | scanf("%d",&d[i]);
| ~~~~~^~~~~~~~~~~~
cake.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
106 | scanf("%d%d",&x,&e);
| ~~~~~^~~~~~~~~~~~~~
cake.cpp:145:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
13 ms |
364 KB |
Output is correct |
| 5 |
Correct |
32 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
752 ms |
876 KB |
Output is correct |
| 2 |
Correct |
457 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
523 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
326 ms |
1004 KB |
Output is correct |
| 5 |
Correct |
825 ms |
1900 KB |
Output is correct |
| 6 |
Correct |
718 ms |
2028 KB |
Output is correct |
| 7 |
Correct |
595 ms |
2028 KB |
Output is correct |
| 8 |
Correct |
371 ms |
2028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
371 ms |
7532 KB |
Output is correct |
| 2 |
Correct |
345 ms |
7404 KB |
Output is correct |
| 3 |
Correct |
342 ms |
7404 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
537 ms |
17644 KB |
Output is correct |
| 6 |
Correct |
544 ms |
17772 KB |
Output is correct |
| 7 |
Correct |
409 ms |
17388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
620 KB |
Output is correct |
| 2 |
Correct |
114 ms |
748 KB |
Output is correct |
| 3 |
Correct |
221 ms |
3820 KB |
Output is correct |
| 4 |
Correct |
262 ms |
3820 KB |
Output is correct |
| 5 |
Correct |
385 ms |
748 KB |
Output is correct |
| 6 |
Correct |
434 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
447 ms |
1516 KB |
Output is correct |
| 8 |
Correct |
358 ms |
7020 KB |
Output is correct |
| 9 |
Execution timed out |
2099 ms |
18536 KB |
Time limit exceeded |
| 10 |
Correct |
1320 ms |
1604 KB |
Output is correct |
| 11 |
Correct |
1494 ms |
3052 KB |
Output is correct |
| 12 |
Execution timed out |
2084 ms |
15212 KB |
Time limit exceeded |
| 13 |
Correct |
1691 ms |
18668 KB |
Output is correct |
