#include "plants.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int SMALL = 300, N = 200000, N_ = 1 << 18, INF = 0x3f3f3f3f;
int max(int a, int b) { return a > b ? a : b; }
int pp[N], hh[N], n, k;
int st[N_ * 2], lz[N_ * 2], first[N_ * 2], last[N_ * 2], gap[N_ * 2], n_, i_;
void put(int i, int x) {
st[i] += x, lz[i] += x;
}
void pul(int i) {
int l = i << 1, r = l | 1;
if (st[l] < st[r])
st[i] = st[l], first[i] = first[l], last[i] = last[l], gap[i] = gap[l];
else if (st[l] > st[r])
st[i] = st[r], first[i] = first[r], last[i] = last[r], gap[i] = gap[r];
else
st[i] = st[l], first[i] = first[l], last[i] = last[r], gap[i] = max(max(gap[l], gap[r]), first[r] == i_ ? 0 : first[r] - last[l]);
st[i] += lz[i];
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void build(vi aa, int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
memset(lz, 0, n_ * 2 * sizeof *lz);
for (i = 0; i < n_; i++) {
st[n_ + i] = i < n ? aa[i] : INF, gap[n_ + i] = 0;
first[n_ + i] = last[n_ + i] = i;
}
for (i = n_ - 1; i > 0; i--)
pul(i);
}
void update(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, x);
if ((r & 1) == 0)
put(r--, x);
}
pull(l_), pull(r_);
}
int get(int k) {
if (gap[1] >= k) {
int i = 1;
while (i < n_)
if (st[i] == st[i << 1 | 0] + lz[i] && gap[i << 1 | 0] >= k)
i = i << 1 | 0;
else if (st[i] == st[i << 1 | 1] + lz[i] && gap[i << 1 | 1] >= k)
i = i << 1 | 1;
else
return first[i << 1 | 1];
}
return first[1] - last[1] + n >= k && first[1] != i_ ? first[1] : -1;
}
char gt[SMALL][SMALL];
void init(int k_, vi rr) {
int h, i;
n = rr.size(), k = k_;
if (n <= SMALL) {
for (i_ = 0; i_ < n; i_++) {
memset(gt[i_], 1, n * sizeof *gt[i_]);
build(rr, n);
for (h = n - 1; h >= 0; h--) {
i = get(k);
if (i == -1)
break;
gt[i_][i] = 0;
update(i, i, INF);
if (i >= k - 1)
update(i - k + 1, i, -1);
else
update(0, i, -1), update(i - k + 1 + n, n - 1, -1);
}
}
} else if (k == 2) {
for (i = 0; i < n; i++)
pp[i] = rr[i];
for (i = 1; i < n; i++)
pp[i] += pp[i - 1];
} else {
build(rr, n);
i_ = -1;
for (h = n - 1; h >= 0; h--) {
i = get(k);
hh[i] = h;
update(i, i, INF);
if (i >= k - 1)
update(i - k + 1, i, -1);
else
update(0, i, -1), update(i - k + 1 + n, n - 1, -1);
}
}
}
int compare_plants(int x, int y) {
if (n <= SMALL)
return !gt[x][y] && !gt[y][x] ? 0 : (gt[x][y] ? 1 : -1);
else if (k == 2) {
int c = pp[y - 1] - (x == 0 ? 0 : pp[x - 1]);
if (c == y - x)
return -1;
else if (c == 0)
return 1;
c = pp[n - 1] - c;
if (c == n - (y - x))
return 1;
else if (c == 0)
return -1;
return 0;
} else
return hh[x] < hh[y] ? -1 : 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
57 ms |
3836 KB |
Output is correct |
7 |
Correct |
69 ms |
4432 KB |
Output is correct |
8 |
Correct |
92 ms |
6044 KB |
Output is correct |
9 |
Correct |
89 ms |
6060 KB |
Output is correct |
10 |
Correct |
89 ms |
6148 KB |
Output is correct |
11 |
Correct |
88 ms |
6076 KB |
Output is correct |
12 |
Correct |
86 ms |
6092 KB |
Output is correct |
13 |
Correct |
85 ms |
6016 KB |
Output is correct |
14 |
Correct |
86 ms |
6056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
216 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
3 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
65 ms |
3652 KB |
Output is correct |
8 |
Correct |
4 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
332 KB |
Output is correct |
10 |
Correct |
64 ms |
3612 KB |
Output is correct |
11 |
Correct |
63 ms |
3504 KB |
Output is correct |
12 |
Correct |
61 ms |
3632 KB |
Output is correct |
13 |
Correct |
64 ms |
3636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
216 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
3 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
65 ms |
3652 KB |
Output is correct |
8 |
Correct |
4 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
332 KB |
Output is correct |
10 |
Correct |
64 ms |
3612 KB |
Output is correct |
11 |
Correct |
63 ms |
3504 KB |
Output is correct |
12 |
Correct |
61 ms |
3632 KB |
Output is correct |
13 |
Correct |
64 ms |
3636 KB |
Output is correct |
14 |
Correct |
87 ms |
4828 KB |
Output is correct |
15 |
Correct |
491 ms |
15404 KB |
Output is correct |
16 |
Correct |
89 ms |
4648 KB |
Output is correct |
17 |
Correct |
489 ms |
15252 KB |
Output is correct |
18 |
Correct |
371 ms |
15168 KB |
Output is correct |
19 |
Correct |
343 ms |
15300 KB |
Output is correct |
20 |
Correct |
503 ms |
15200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
60 ms |
3164 KB |
Output is correct |
4 |
Correct |
259 ms |
15324 KB |
Output is correct |
5 |
Correct |
270 ms |
15172 KB |
Output is correct |
6 |
Correct |
319 ms |
15308 KB |
Output is correct |
7 |
Correct |
376 ms |
15256 KB |
Output is correct |
8 |
Correct |
481 ms |
15408 KB |
Output is correct |
9 |
Correct |
262 ms |
15284 KB |
Output is correct |
10 |
Correct |
269 ms |
15212 KB |
Output is correct |
11 |
Correct |
84 ms |
4952 KB |
Output is correct |
12 |
Correct |
245 ms |
15176 KB |
Output is correct |
13 |
Correct |
333 ms |
15244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
288 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
5 ms |
460 KB |
Output is correct |
7 |
Correct |
51 ms |
1244 KB |
Output is correct |
8 |
Correct |
42 ms |
1264 KB |
Output is correct |
9 |
Correct |
46 ms |
1272 KB |
Output is correct |
10 |
Correct |
38 ms |
1348 KB |
Output is correct |
11 |
Correct |
51 ms |
1360 KB |
Output is correct |
12 |
Correct |
41 ms |
1360 KB |
Output is correct |
13 |
Correct |
44 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
57 ms |
3836 KB |
Output is correct |
7 |
Correct |
69 ms |
4432 KB |
Output is correct |
8 |
Correct |
92 ms |
6044 KB |
Output is correct |
9 |
Correct |
89 ms |
6060 KB |
Output is correct |
10 |
Correct |
89 ms |
6148 KB |
Output is correct |
11 |
Correct |
88 ms |
6076 KB |
Output is correct |
12 |
Correct |
86 ms |
6092 KB |
Output is correct |
13 |
Correct |
85 ms |
6016 KB |
Output is correct |
14 |
Correct |
86 ms |
6056 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
216 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
332 KB |
Output is correct |
21 |
Correct |
65 ms |
3652 KB |
Output is correct |
22 |
Correct |
4 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
332 KB |
Output is correct |
24 |
Correct |
64 ms |
3612 KB |
Output is correct |
25 |
Correct |
63 ms |
3504 KB |
Output is correct |
26 |
Correct |
61 ms |
3632 KB |
Output is correct |
27 |
Correct |
64 ms |
3636 KB |
Output is correct |
28 |
Correct |
87 ms |
4828 KB |
Output is correct |
29 |
Correct |
491 ms |
15404 KB |
Output is correct |
30 |
Correct |
89 ms |
4648 KB |
Output is correct |
31 |
Correct |
489 ms |
15252 KB |
Output is correct |
32 |
Correct |
371 ms |
15168 KB |
Output is correct |
33 |
Correct |
343 ms |
15300 KB |
Output is correct |
34 |
Correct |
503 ms |
15200 KB |
Output is correct |
35 |
Correct |
0 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
60 ms |
3164 KB |
Output is correct |
38 |
Correct |
259 ms |
15324 KB |
Output is correct |
39 |
Correct |
270 ms |
15172 KB |
Output is correct |
40 |
Correct |
319 ms |
15308 KB |
Output is correct |
41 |
Correct |
376 ms |
15256 KB |
Output is correct |
42 |
Correct |
481 ms |
15408 KB |
Output is correct |
43 |
Correct |
262 ms |
15284 KB |
Output is correct |
44 |
Correct |
269 ms |
15212 KB |
Output is correct |
45 |
Correct |
84 ms |
4952 KB |
Output is correct |
46 |
Correct |
245 ms |
15176 KB |
Output is correct |
47 |
Correct |
333 ms |
15244 KB |
Output is correct |
48 |
Correct |
0 ms |
332 KB |
Output is correct |
49 |
Correct |
0 ms |
332 KB |
Output is correct |
50 |
Correct |
0 ms |
332 KB |
Output is correct |
51 |
Correct |
1 ms |
288 KB |
Output is correct |
52 |
Correct |
1 ms |
292 KB |
Output is correct |
53 |
Correct |
5 ms |
460 KB |
Output is correct |
54 |
Correct |
51 ms |
1244 KB |
Output is correct |
55 |
Correct |
42 ms |
1264 KB |
Output is correct |
56 |
Correct |
46 ms |
1272 KB |
Output is correct |
57 |
Correct |
38 ms |
1348 KB |
Output is correct |
58 |
Correct |
51 ms |
1360 KB |
Output is correct |
59 |
Correct |
41 ms |
1360 KB |
Output is correct |
60 |
Correct |
44 ms |
1272 KB |
Output is correct |
61 |
Incorrect |
60 ms |
4904 KB |
Output isn't correct |
62 |
Halted |
0 ms |
0 KB |
- |