| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257767 |
2020-08-04T18:07:48 Z |
doowey |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
4088 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 250010;
int A[N];
int tree[N * 4 + 512];
void upd(int node, int cl, int cr, int pos, int x){
if(cl == cr){
tree[node] = x;
return;
}
int mid = (cl + cr) / 2;
if(mid >= pos)
upd(node * 2, cl, mid, pos, x);
else
upd(node * 2 + 1, mid + 1, cr, pos, x);
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
int ask(int node, int cl, int cr, int tl, int tr){
if(cr < tl)
return 0;
if(cl > tr)
return 0;
if(cl >= tl && cr <= tr)
return tree[node];
int mid = (cl + cr) / 2;
return max(ask(node * 2, cl, mid, tl, tr), ask(node * 2 + 1, mid + 1, cr, tl, tr));
}
int getrng(int node, int cl, int cr, int tl, int tr, int mode, int vlx){
if(tl > tr || tree[node] < vlx)
return -1;
if(cr < tl)
return -1;
if(cl > tr)
return -1;
if(cl >= tl && cr <= tr){
if(cl==cr){
if(tree[node] < vlx) return -1;
return cl;
}
if(mode == 0){ // to left
int mid = (cl + cr) / 2;
if(tree[node * 2] > vlx)
return getrng(node * 2, cl, mid, tl, tr, mode, vlx);
if(tree[node * 2 + 1] > vlx)
return getrng(node * 2 + 1, mid + 1, cr, tl, tr,mode, vlx);
return -1;
}
else{
int mid = (cl + cr) / 2;
if(tree[node * 2 + 1] > vlx){
return getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
}
if(tree[node * 2] > vlx)
return getrng(node * 2, cl, mid, tl, tr, mode, vlx);
return -1;
}
}
int mid = (cl + cr) / 2;
int f1,f2;
if(mode == 0){
f1 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
if(f1 != -1) return f1;
f2 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
return f2;
}
else{
f1 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
if(f1 != -1) return f1;
f2 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
return f2;
}
}
int main(){
fastIO;
int n, st;
cin >> n >> st;
for(int i = 1; i <= n; i ++ ){
cin >> A[i];
upd(1, 1, n, i, A[i]);
}
vector<int> cc;
for(int j = 0 ; j < 10 ; j ++ ){
for(int i = 1; i <= n; i ++ ){
if(n - j == A[i]){
cc.push_back(i);
break;
}
}
}
int q;
cin >> q;
int nx;
int res;
char typ;
int mx;
int ly;
int li;
int nw = n;
int sz;
int pp;
vector<int> niw;
for(int i = 1; i <= q; i ++ ){
cin >> typ;
if(typ == 'F'){
cin >> nx;
res = 1;
if(nx > st){
res += nx - st;
mx = ask(1, 1, n, st + 1, nx);
ly = getrng(1,1,n,1,st-1,1,mx);
if(ly == -1) ly = 0;
res += st - ly - 1;
}
else if(nx < st){
res += st - nx;
mx = ask(1, 1, n,nx, st - 1);
ly = getrng(1,1,n,st+1,n,0,mx);
if(ly == -1) ly = n + 1;
res += ly - st - 1;
}
cout << res - 1 << "\n";
}
else{
cin >> nx >> mx;
mx -- ;
if(cc[mx] == nx) continue;
nw += 10;
niw.clear();
for(int p = 0 ; p < cc.size(); p ++ ){
if(cc[p] == nx) continue;
if(p == mx){
sz = niw.size();
pp = nw - sz;
upd(1, 1, n, nx, pp);
niw.push_back(nx);
}
sz = niw.size();
pp = nw - sz;
upd(1, 1, n, cc[p], pp);
niw.push_back(cc[p]);
}
cc = niw;
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:146:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p = 0 ; p < cc.size(); p ++ ){
~~^~~~~~~~~~~
cake.cpp:114:9: warning: unused variable 'li' [-Wunused-variable]
int li;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
368 KB |
Output is correct |
| 4 |
Correct |
152 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1547 ms |
624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2093 ms |
632 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2092 ms |
636 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2097 ms |
632 KB |
Time limit exceeded |
| 4 |
Correct |
522 ms |
760 KB |
Output is correct |
| 5 |
Execution timed out |
2091 ms |
756 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2093 ms |
760 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2099 ms |
760 KB |
Time limit exceeded |
| 8 |
Correct |
647 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
2296 KB |
Output is correct |
| 2 |
Correct |
79 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
76 ms |
2244 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
110 ms |
4088 KB |
Output is correct |
| 6 |
Correct |
125 ms |
4088 KB |
Output is correct |
| 7 |
Correct |
123 ms |
3832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2090 ms |
528 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2086 ms |
648 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2094 ms |
1528 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2094 ms |
1400 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2076 ms |
632 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2091 ms |
1272 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2087 ms |
712 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2096 ms |
1912 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2089 ms |
3568 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2094 ms |
572 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2091 ms |
1016 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2071 ms |
3336 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2100 ms |
3448 KB |
Time limit exceeded |
