| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 155824 |
2019-09-30T16:40:13 Z |
Akashi |
Cake (CEOI14_cake) |
C++14 |
|
1310 ms |
8536 KB |
#include <bits/stdc++.h>
using namespace std;
int n, a;
int pos[10];
int x[250005];
int Arb[1000005], Lazy[1000005];
void propag(int nod){
Lazy[nod * 2] += Lazy[nod];
Lazy[nod * 2 + 1] += Lazy[nod];
Arb[nod * 2] += Lazy[nod];
Arb[nod * 2 + 1] += Lazy[nod];
Lazy[nod] = 0;
}
void build(int st = 1, int dr = n, int nod = 1){
if(st == dr){
Arb[nod] = x[st];
return ;
}
int mij = (st + dr) / 2;
build(st, mij, nod * 2);
build(mij + 1, dr, nod * 2 + 1);
Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}
void update(int x, int y, int v, int st = 1, int dr = n, int nod = 1){
if(x <= st && dr <= y){
Lazy[nod] += v;
return ;
}
propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) update(x, y, v, st, mij, nod * 2);
if(mij + 1 <= y) update(x, y, v, mij + 1, dr, nod * 2 + 1);
Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}
void update2(int x, int v, int st = 1, int dr = n, int nod = 1){
if(st == dr){
Arb[nod] = v;
return ;
}
propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) update2(x, v, st, mij, nod * 2);
else update2(x, v, mij + 1, dr, nod * 2 + 1);
Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}
int query(int x, int y, int st = 1, int dr = n, int nod = 1){
if(x <= st && dr <= y) return Arb[nod];
propag(nod);
int mij = (st + dr) / 2;
int a1 = n + 1, a2 = n + 1;
if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);
Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
return min(a1, a2);
}
int query2(int sgn, int x, int y, int val, int st = 1, int dr = n, int nod = 1){
if(dr < x) return x - 1;
if(st > y) return y + 1;
if(st == dr){
if(Arb[nod] >= val) return st;
return st + sgn;
}
propag(nod);
int mij = (st + dr) / 2;
if(sgn == -1){
if(Arb[nod * 2] >= val) return query2(sgn, x, y, val, mij + 1, dr, nod * 2 + 1);
return query2(sgn, x, y, val, st, mij, nod * 2);
}
else{
if(Arb[nod * 2 + 1] >= val) return query2(sgn, x, y, val, st, mij, nod * 2);
return query2(sgn, x, y, val, mij + 1, dr, nod * 2 + 1);
}
Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}
int main()
{
scanf("%d%d", &n, &a);
for(int i = 1; i <= n ; ++i){
scanf("%d", &x[i]), x[i] = n - x[i] + 1;
if(x[i] <= 10) pos[x[i]] = i;
}
build();
int q;
scanf("%d", &q);
char c;
int x, y;
while(q--){
scanf("\n%c", &c);
if(c == 'F'){
scanf("%d", &x);
if(x == a){
printf("0\n");
continue ;
}
int val = query(min(x, a + 1), max(x, a - 1));
int st = 1, dr = a - 1, sgn = 1;
if(x < a) st = a + 1, dr = n, sgn = -1;
int p = query2(sgn, st, dr, val);
int Sol = abs(x - a) + abs(p - a);
printf("%d\n", Sol);
}
else{
scanf("%d%d", &x, &y);
int p = 11;
for(int i = 1; i <= 10 ; ++i)
if(pos[i] == x) p = i;
if(p == 11){
update(1, n, 1);
for(int i = 1; i < y ; ++i) update2(pos[i], i);
for(int i = 10; i >= y ; --i) pos[i] = pos[i - 1];
update2(x, y);
pos[y] = x;
}
else{
if(p == y) continue ;
for(int i = p; i < 10 ; ++i){
if(i >= n) continue ;
pos[i] = pos[i + 1];
update2(pos[i], i);
}
for(int i = 10; i > y ; --i){
if(i > n) continue ;
pos[i] = pos[i - 1];
update2(pos[i], i);
}
pos[y] = x;
update2(x, y);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &a);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:100:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x[i]), x[i] = n - x[i] + 1;
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c", &c);
~~~~~^~~~~~~~~~~~
cake.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
cake.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:135:25: warning: iteration 9 invokes undefined behavior [-Waggressive-loop-optimizations]
if(pos[i] == x) p = i;
~~~~~^
cake.cpp:134:30: note: within this loop
for(int i = 1; i <= 10 ; ++i)
~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
960 ms |
2204 KB |
Output isn't correct |
| 2 |
Incorrect |
1074 ms |
2272 KB |
Output isn't correct |
| 3 |
Incorrect |
952 ms |
2368 KB |
Output isn't correct |
| 4 |
Incorrect |
1149 ms |
2260 KB |
Output isn't correct |
| 5 |
Incorrect |
1033 ms |
2408 KB |
Output isn't correct |
| 6 |
Incorrect |
1054 ms |
2296 KB |
Output isn't correct |
| 7 |
Incorrect |
1047 ms |
2476 KB |
Output isn't correct |
| 8 |
Incorrect |
1310 ms |
2432 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
4700 KB |
Output isn't correct |
| 2 |
Incorrect |
109 ms |
4712 KB |
Output isn't correct |
| 3 |
Incorrect |
100 ms |
4700 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
153 ms |
7632 KB |
Output isn't correct |
| 6 |
Incorrect |
144 ms |
7580 KB |
Output isn't correct |
| 7 |
Incorrect |
110 ms |
7292 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
1016 KB |
Output isn't correct |
| 2 |
Incorrect |
40 ms |
964 KB |
Output isn't correct |
| 3 |
Incorrect |
84 ms |
2680 KB |
Output isn't correct |
| 4 |
Incorrect |
101 ms |
2552 KB |
Output isn't correct |
| 5 |
Incorrect |
135 ms |
1784 KB |
Output isn't correct |
| 6 |
Incorrect |
161 ms |
3576 KB |
Output isn't correct |
| 7 |
Incorrect |
160 ms |
2684 KB |
Output isn't correct |
| 8 |
Incorrect |
513 ms |
4356 KB |
Output isn't correct |
| 9 |
Incorrect |
811 ms |
8536 KB |
Output isn't correct |
| 10 |
Incorrect |
454 ms |
3064 KB |
Output isn't correct |
| 11 |
Incorrect |
562 ms |
3960 KB |
Output isn't correct |
| 12 |
Incorrect |
796 ms |
8132 KB |
Output isn't correct |
| 13 |
Incorrect |
911 ms |
8368 KB |
Output isn't correct |
