| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 336797 |
2020-12-16T20:41:54 Z |
nafis_shifat |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
25068 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);
}
return min(queryL(left,b,mid,p,x),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);
}
return max(queryR(left,b,mid,p,x),queryR(right,mid+1,e,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;
cin>>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:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid=b+e>>1;
| ~^~
cake.cpp: In member function 'int segtree::query(int, int, int, int, int)':
cake.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid=b+e>>1;
| ~^~
cake.cpp: In function 'int main()':
cake.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | scanf("%d",&d[i]);
| ~~~~~^~~~~~~~~~~~
cake.cpp:140:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
140 | 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 |
14 ms |
492 KB |
Output is correct |
| 5 |
Correct |
35 ms |
1132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
885 ms |
5372 KB |
Output is correct |
| 2 |
Correct |
591 ms |
5484 KB |
Output is correct |
| 3 |
Correct |
646 ms |
5612 KB |
Output is correct |
| 4 |
Correct |
448 ms |
5484 KB |
Output is correct |
| 5 |
Correct |
958 ms |
6636 KB |
Output is correct |
| 6 |
Correct |
865 ms |
7020 KB |
Output is correct |
| 7 |
Correct |
720 ms |
6892 KB |
Output is correct |
| 8 |
Correct |
504 ms |
7020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
383 ms |
9064 KB |
Output is correct |
| 2 |
Correct |
345 ms |
8940 KB |
Output is correct |
| 3 |
Correct |
343 ms |
8940 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
549 ms |
20076 KB |
Output is correct |
| 6 |
Correct |
539 ms |
20076 KB |
Output is correct |
| 7 |
Correct |
451 ms |
20076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
125 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
230 ms |
4972 KB |
Output is correct |
| 4 |
Correct |
274 ms |
4844 KB |
Output is correct |
| 5 |
Correct |
416 ms |
1900 KB |
Output is correct |
| 6 |
Correct |
462 ms |
7020 KB |
Output is correct |
| 7 |
Correct |
482 ms |
3180 KB |
Output is correct |
| 8 |
Correct |
417 ms |
9732 KB |
Output is correct |
| 9 |
Execution timed out |
2065 ms |
24408 KB |
Time limit exceeded |
| 10 |
Correct |
1397 ms |
5324 KB |
Output is correct |
| 11 |
Correct |
1585 ms |
7404 KB |
Output is correct |
| 12 |
Execution timed out |
2095 ms |
21228 KB |
Time limit exceeded |
| 13 |
Correct |
1821 ms |
25068 KB |
Output is correct |
