#include <bits/stdc++.h>
#include "plants.h"
#define x first
#define y second
using ll = long long;
using namespace std;
const int LG = 18, N = 1 << LG;
int st1[2 * N], st2[2 * N], lz1[2 * N], lz2[2 * N], timer = 1, fndl[2 * N], used3[N], level[N], kk, nn;
pair<int, int> fnd[2 * N], binupl[LG][N], binupr[LG][N];
vector<pair<int, int>> mst[2 * N];
void push(int i, int st[], int lz[]) {
if (lz[i] != -1) {
st[2 * i + 1] = lz[i];
st[2 * i + 2] = lz[i];
lz[2 * i + 1] = lz[i];
lz[2 * i + 2] = lz[i];
lz[i] = -1;
}
}
void set_seg(int l, int r, int x, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
st[i] = x;
lz[i] = x;
return;
}
if (l1 > r || r1 < l) {
return;
}
push(i, st, lz);
set_seg(l, r, x, st, lz, l1, (l1 + r1) / 2, 2 * i + 1);
set_seg(l, r, x, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
st[i] = min(st[2 * i + 1], st[2 * i + 2]);
}
int get(int ind, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 == ind && r1 == ind) {
return st[i];
}
if (l1 > ind || r1 < ind) {
return INT32_MAX;
}
push(i, st, lz);
return min(get(ind, st, lz, l1, (l1 + r1) / 2, 2 * i + 1), get(ind, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}
void push(int i) {
fnd[2 * i + 1].x += fndl[i];
fnd[2 * i + 2].x += fndl[i];
fndl[2 * i + 1] += fndl[i];
fndl[2 * i + 2] += fndl[i];
fndl[i] = 0;
}
void add_seg(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
fnd[i].x += x;
fndl[i] += x;
return;
}
if (l1 > r || r1 < l) {
return;
}
push(i);
add_seg(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
add_seg(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
fnd[i] = min(fnd[2 * i + 1], fnd[2 * i + 2]);
}
pair<int, int> get_min(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
return fnd[i];
}
if (l1 > r || r1 < l) {
return {INT32_MAX, -1};
}
push(i);
return min(get_min(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}
pair<int, int> find_max(int i, int v) {
int l = -1, r = mst[i].size();
while (r - l > 1) {
int m = (r + l) / 2;
if (mst[i][m].x >= v) {
r = m;
} else {
l = m;
}
}
return l == -1 ? make_pair(-1, i) : mst[i][l];
}
pair<int, int> get_max(int l, int r, int v) {
l += N - 1;
r += N - 1;
pair<int, int> res = {-1, -1};
while (l <= r) {
if (~l & 1) {
res = max(res, find_max(l++, v));
}
if (r & 1) {
res = max(res, find_max(r--, v));
}
l = (l - 1) / 2;
r = (r - 1) / 2;
}
return res;
}
void mrg(int to, int a, int b) {
mst[to].resize(mst[a].size() + mst[b].size());
std::merge(mst[a].begin(), mst[a].end(), mst[b].begin(), mst[b].end(), mst[to].begin());
}
void init(int k, vector<int> r) {
kk = k;
int n = r.size();
nn = n;
int ok = 0;
for (int i = 0; i < 2 * N; i++) {
st1[i] = -1;
st2[i] = -1;
lz1[i] = -1;
lz2[i] = -1;
}
for (int i = 0; i < N; i++) {
fnd[i + N - 1].y = i;
level[i] = N;
}
for (int i = 0; i < n; i++) {
add_seg(i, i, r[i]);
if (r[i] == 0) {
used3[i] = 1;
if (i + k > n) {
add_seg(i + 1, n - 1, 1);
add_seg(0, i + k - n - 1, 1);
} else {
add_seg(i + 1, i + k - 1, 1);
}
}
}
while (ok < n) {
auto [value, i] = get_min(0, n - 1);
if (value) {
exit(1);
}
int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2);
if (tmp1 != -1) {
level[i] = min(level[i], level[tmp1] - 1);
}
if (tmp2 != -1) {
level[i] = min(level[i], level[tmp2] - 1);
}
vector<int> z;
if (i + k - 1 < n) {
set_seg(i + 1, i + k - 1, i, st2, lz2);
add_seg(i + 1, i + k - 1, -1);
} else {
set_seg(i + 1, n - 1, i, st2, lz2);
set_seg(0, i + k - 1 - n, i, st2, lz2);
add_seg(i + 1, n - 1, -1);
add_seg(0, i + k - 1 - n, -1);
}
if (i >= k - 1) {
add_seg(i - k + 1, i - 1, -1);
int left = i - k + 1;
while (left <= i - 1 && !get_min(left, i - 1).x) {
z.push_back(get_min(left, i - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
set_seg(i - k + 1, i - 1, i, st1, lz1);
} else {
add_seg(0, i - 1, -1);
set_seg(0, i - 1, i, st1, lz1);
add_seg(n + 1 - k + i, n - 1, -1);
set_seg(n + 1 - k + i, n - 1, i, st1, lz1);
int left = 0;
while (left <= i - 1 && !get_min(left, i - 1).x) {
z.push_back(get_min(left, i - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
left = n + 1 - k + i;
while (left <= n - 1 && !get_min(left, n - 1).x) {
z.push_back(get_min(left, n - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
}
if (i + k - 1 < n) {
int left = i + 1;
while (left <= i + k - 1 && !get_min(left, i + k - 1).x) {
z.push_back(get_min(left, i + k - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
} else {
int left = i + 1;
while (left <= n - 1 && !get_min(left, n - 1).x) {
z.push_back(get_min(left, n - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
left = 0;
while (left <= i + k - 1 - n && !get_min(left, i + k - 1 - n).x) {
z.push_back(get_min(left, i + k - 1 - n).y);
assert(left <= z.back());
left = z.back() + 1;
}
}
for (int j : z) {
if (!used3[j]) {
if (j + k > n) {
add_seg(j + 1, n - 1, 1);
add_seg(0, j + k - n - 1, 1);
} else {
add_seg(j + 1, j + k - 1, 1);
}
used3[j] = 1;
}
}
add_seg(i, i, INT32_MAX / 2);
ok++;
}
for (int i = 0; i < n; i++) {
mst[N - 1 + i].emplace_back(level[i], i);
}
for (int i = N - 2; i >= 0; i--) {
mrg(i, 2 * i + 1, 2 * i + 2);
}
for (int i = 0; i < n; i++) {
if (i >= k - 1) {
binupl[0][i].x = get_max(i - k + 1, i - 1, level[i]).y;
} else {
binupl[0][i].x = max(get_max(0, i - 1, level[i]), get_max(n - i + k - 1, n - 1, level[i])).y;
}
binupl[0][i].y = i - binupl[0][i].x;
if (binupl[0][i].y < 0) {
binupl[0][i].y += n;
}
if (i + k - 1 < n) {
binupr[0][i].x = get_max(i + 1, i + k - 1, level[i]).y;
} else {
binupr[0][i].x = max(get_max(i + 1, n - 1, level[i]), get_max(0, i + k - 1 - n, level[i])).y;
}
binupr[0][i].y = binupr[0][i].x - i;
if (binupr[0][i].y < 0) {
binupr[0][i].y += n;
}
}
for (int l = 1; l < LG; l++) {
for (int i = 0; i < n; i++) {
binupl[l][i].x = binupl[i - 1][binupl[i - 1][i].x].x;
binupr[l][i].x = binupr[i - 1][binupr[i - 1][i].x].x;
binupl[l][i].y = binupl[i - 1][binupl[i - 1][i].x].y + binupl[i - 1][i].y;
binupr[l][i].y = binupr[i - 1][binupr[i - 1][i].x].y + binupr[i - 1][i].y;
}
}
}
bool try_compare(int x, int y) {
int dist = x - y, nw = x;
if (dist < 0) {
dist += nn;
}
dist -= kk - 1;
if (level[nw] > level[y] && dist <= 0) {
return true;
}
for (int i = LG - 1; i >= 0; i--) {
if (binupl[i][nw].y < dist) {
dist -= binupl[i][nw].y;
nw = binupl[i][nw].x;
}
}
dist -= binupl[0][nw].y;
nw = binupl[0][nw].y;
if (level[nw] > level[y] && dist <= 0) {
return true;
}
dist = y - x, nw = x;
if (dist < 0) {
dist += nn;
}
dist -= kk - 1;
if (level[nw] > level[y] && dist <= 0) {
return true;
}
for (int i = LG - 1; i >= 0; i--) {
if (binupr[i][nw].y < dist) {
dist -= binupr[i][nw].y;
nw = binupr[i][nw].x;
}
}
dist -= binupr[0][nw].y;
nw = binupr[0][nw].y;
if (level[nw] > level[y] && dist <= 0) {
return true;
}
return false;
}
int compare_plants(int x, int y) {
if (try_compare(x, y)) {
return 1;
}
if (try_compare(y, x)) {
return -1;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
100948 KB |
Output is correct |
| 2 |
Correct |
15 ms |
100964 KB |
Output is correct |
| 3 |
Correct |
15 ms |
96860 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
84396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
100956 KB |
Output is correct |
| 2 |
Correct |
16 ms |
100844 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
96860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
100956 KB |
Output is correct |
| 2 |
Correct |
16 ms |
100844 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
96860 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
92540 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
31068 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
100956 KB |
Output is correct |
| 2 |
Correct |
15 ms |
100956 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
88668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
100952 KB |
Output is correct |
| 2 |
Correct |
15 ms |
100956 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
92808 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
100948 KB |
Output is correct |
| 2 |
Correct |
15 ms |
100964 KB |
Output is correct |
| 3 |
Correct |
15 ms |
96860 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
84396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
