#include <bits/stdc++.h>
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], free = 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;
}
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++;
used[s] = 1;
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] = free++;
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] = free++;
g[twin[tmp2]].push_back(twin[i]);
}
} else if (tmp2 != -1 && !used2[tmp2]) {
assert(cnt == 1);
twin[i] = free++;
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:9:123: error: 'int free' redeclared as different kind of entity
9 | 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], free = N / 2;
| ^~~~
In file included from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from plants.cpp:1:
/usr/include/stdlib.h:565:13: note: previous declaration 'void free(void*)'
565 | extern void free (void *__ptr) __THROW;
| ^~~~
plants.cpp: In function 'void push(int)':
plants.cpp:49:17: error: 'struct std::pair<int, int>' has no member named 'x'
49 | fnd[2 * i + 1].x += fndl[i];
| ^
plants.cpp:50:17: error: 'struct std::pair<int, int>' has no member named 'x'
50 | fnd[2 * i + 2].x += fndl[i];
| ^
plants.cpp: In function 'void add_seg(int, int, int, int, int, int)':
plants.cpp:58:10: error: 'struct std::pair<int, int>' has no member named 'x'
58 | fnd[i].x += x;
| ^
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/stdint.h:9,
from /usr/include/c++/10/cstdint:41,
from /usr/include/c++/10/bits/char_traits.h:685,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from plants.cpp:1:
plants.cpp: In function 'std::pair<int, int> get_min(int, int, int, int, int)':
plants.cpp:76:10: error: could not convert '2147483647' from 'int' to 'std::pair<int, int>'
76 | return INT32_MAX;
| ^~~~~~~~~
| |
| int
plants.cpp: In function 'void dfs(int, int)':
plants.cpp:84:2: error: 'used' was not declared in this scope; did you mean 'used2'?
84 | used[s] = 1;
| ^~~~
| used2
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:125:18: warning: ISO C++ forbids incrementing a pointer of type 'void (*)(void*) noexcept' [-Wpointer-arith]
125 | twin[i] = free++;
| ^~~~
plants.cpp:125:18: error: lvalue required as increment operand
plants.cpp:134:18: warning: ISO C++ forbids incrementing a pointer of type 'void (*)(void*) noexcept' [-Wpointer-arith]
134 | twin[i] = free++;
| ^~~~
plants.cpp:134:18: error: lvalue required as increment operand
plants.cpp:139:17: warning: ISO C++ forbids incrementing a pointer of type 'void (*)(void*) noexcept' [-Wpointer-arith]
139 | twin[i] = free++;
| ^~~~
plants.cpp:139:17: error: lvalue required as increment operand
plants.cpp:147:53: error: 'struct std::pair<int, int>' has no member named 'x'
147 | while (left <= i - 1 && !get_min(left, i - 1).x) {
| ^
plants.cpp:148:41: error: 'struct std::pair<int, int>' has no member named 'y'
148 | z.push_back(get_min(left, i - 1).y);
| ^
plants.cpp:167:53: error: 'struct std::pair<int, int>' has no member named 'x'
167 | while (left <= i - 1 && !get_min(left, i - 1).x) {
| ^
plants.cpp:168:41: error: 'struct std::pair<int, int>' has no member named 'y'
168 | z.push_back(get_min(left, i - 1).y);
| ^
plants.cpp:172:53: error: 'struct std::pair<int, int>' has no member named 'x'
172 | while (left <= n - 1 && !get_min(left, n - 1).x) {
| ^
plants.cpp:173:41: error: 'struct std::pair<int, int>' has no member named 'y'
173 | z.push_back(get_min(left, n - 1).y);
| ^
plants.cpp:95:17: warning: unused variable 'last' [-Wunused-variable]
95 | int ok = 0, last, lev = n, iter = 0;
| ^~~~
plants.cpp:95:23: warning: unused variable 'lev' [-Wunused-variable]
95 | int ok = 0, last, lev = n, iter = 0;
| ^~~
plants.cpp:95:32: warning: unused variable 'iter' [-Wunused-variable]
95 | int ok = 0, last, lev = n, iter = 0;
| ^~~~
