#include <bits/stdc++.h>
#define x first
#define y second
using ll = long long;
using namespace std;
const int N = 1 << 19;
vector<int> g[N];
int st1[2 * N], st2[2 * N], lz1[2 * N], lz2[2 * N], twin[N], tin[N], tout[N], timer = 1, fndl[2 * N], used1[N], used2[N], fre = N / 2;
pair<int, int> fnd[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));
}
void dfs(int s, int p) {
tin[s] = timer++;
for (int i : g[s]) {
if (i != p) {
dfs(i, s);
}
}
tout[s] = timer++;
}
void init(int k, vector<int> r) {
int n = r.size();
int ok = 0, last, lev = n, iter = 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++) {
twin[i] = -1;
}
for (int i = 0; i < n; i++) {
add_seg(i, i, r[i]);
if (r[i] == 0) {
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);
assert(value == 0);
int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2), cnt = 0;
if (tmp1 != -1 && !used1[tmp1]) {
g[tmp1].push_back(i);
used1[tmp1] = 1;
cnt++;
if (twin[tmp1] != -1) {
twin[i] = fre++;
g[twin[tmp1]].push_back(twin[i]);
cnt++;
}
}
if (tmp2 != -1 && !used2[tmp2] && !cnt) {
g[tmp2].push_back(i);
used2[tmp2] = 1;
if (twin[tmp2] != -1) {
twin[i] = fre++;
g[twin[tmp2]].push_back(twin[i]);
}
} else if (tmp2 != -1 && !used2[tmp2]) {
assert(cnt == 1);
twin[i] = fre++;
g[tmp2].push_back(twin[i]);
used2[tmp2] = 1;
}
if (i >= k - 1) {
add_seg(i - k + 1, i - 1, -1);
int left = i - k + 1;
vector<int> z;
while (left <= i - 1 && !get_min(left, i - 1).x) {
z.push_back(get_min(left, i - 1).y);
left = z.back() + 1;
}
for (int j : z) {
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);
}
}
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;
vector<int> z;
while (left <= i - 1 && !get_min(left, i - 1).x) {
z.push_back(get_min(left, i - 1).y);
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);
left = z.back() + 1;
}
for (int j : z) {
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);
}
}
}
// for (int j = i - 1; j > i - k; j--) {
// if (j >= 0) {
// nw[j]--;
// tmp1[j] = i;
// } else {
// nw[j + n]--;
// tmp1[j + n] = i;
// }
// }
if (i + k - 1 < n) {
set_seg(i + 1, i + k - 1, i, st2, lz2);
} else {
set_seg(i + 1, n - 1, i, st2, lz2);
set_seg(0, i + k - 1 - n, i, st2, lz2);
}
// for (int j = i + 1; j < i + k; j++) {
// if (j < n) {
// tmp2[j] = i;
// } else {
// tmp2[j - n] = i;
// }
// }
add_seg(i, i, INT32_MAX / 2);
// nw[i] = INT32_MAX / 2;
ok++;
}
for (int i = 0; i < N; i++) {
if (!tin[i]) {
dfs(i, -1);
}
}
}
int compare_plants(int x, int y) {
vector<int> xx(1, x), yy(1, y);
if (twin[x] != -1) {
xx.push_back(twin[x]);
}
if (twin[y] != -1) {
yy.push_back(twin[y]);
}
for (int y1 : yy) {
for (int x1 : xx) {
if (tin[y1] < tin[x1] && tout[y1] > tin[x1]) {
return -1;
}
}
}
// if (clc[y][x]) {
// return -1;
// }
for (int y1 : xx) {
for (int x1 : yy) {
if (tin[y1] < tin[x1] && tout[y1] > tin[x1]) {
return 1;
}
}
}
return 0;
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:97:17: warning: unused variable 'last' [-Wunused-variable]
97 | int ok = 0, last, lev = n, iter = 0;
| ^~~~
plants.cpp:97:23: warning: unused variable 'lev' [-Wunused-variable]
97 | int ok = 0, last, lev = n, iter = 0;
| ^~~
plants.cpp:97:32: warning: unused variable 'iter' [-Wunused-variable]
97 | int ok = 0, last, lev = n, iter = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4041 ms |
106312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4053 ms |
106036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4053 ms |
106036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4035 ms |
106868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4018 ms |
106388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4030 ms |
105756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4041 ms |
106312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
