| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257765 |
2020-08-04T18:04:16 Z |
doowey |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
5368 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);
f2 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
}
else{
f2 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
f1 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
}
if(f1 != -1) return f1;
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:144:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p = 0 ; p < cc.size(); p ++ ){
~~^~~~~~~~~~~
cake.cpp:112:9: warning: unused variable 'li' [-Wunused-variable]
int li;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
163 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1497 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
1016 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2077 ms |
1148 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2089 ms |
1016 KB |
Time limit exceeded |
| 4 |
Correct |
513 ms |
1912 KB |
Output is correct |
| 5 |
Execution timed out |
2084 ms |
1156 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2096 ms |
1272 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2084 ms |
1300 KB |
Time limit exceeded |
| 8 |
Correct |
631 ms |
2388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
3704 KB |
Output is correct |
| 2 |
Correct |
84 ms |
3576 KB |
Output is correct |
| 3 |
Correct |
78 ms |
3576 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
125 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
131 ms |
5340 KB |
Output is correct |
| 7 |
Correct |
112 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2072 ms |
996 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2080 ms |
1196 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2096 ms |
1656 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2085 ms |
2040 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2086 ms |
1080 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2063 ms |
2180 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2088 ms |
1184 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2071 ms |
2840 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2040 ms |
4984 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2073 ms |
1092 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2067 ms |
1396 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2068 ms |
4980 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2097 ms |
4856 KB |
Time limit exceeded |
