#include "plants.h"
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 200000, N_ = 1 << 18, INF = 0x3f3f3f3f;
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int pp[N], ii[N], n, k;
int st[N_ * 2], lz[N_ * 2], first[N_ * 2], last[N_ * 2], gap[N_ * 2], n_;
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] == first[r] - last[l]);
st[i] += lz[i];
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
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) {
int i = 1;
if (gap[1] < k)
return first[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 -1;
}
void update_(int l, int r, int x) {
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
st[l++] = x;
if ((r & 1) == 0)
st[r--] = x;
}
}
int query_(int i) {
int x = INF;
for (i += n_; i > 0; i >>= 1)
x = min(x, st[i]);
return x;
}
int *ej[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
char root[N]; int ta[2][N], tb[2][N], mode, time;
void dfs(int p, int i) {
int o;
ta[mode][i] = time++;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs(i, j);
}
tb[mode][i] = time;
}
void init(int k_, vi rr) {
int h, i;
n = rr.size(), k = k_;
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n_; i++) {
st[n_ + i] = i < n ? rr[i] : INF, gap[n_ + i] = 0;
first[n_ + i] = last[n_ + i] = i;
}
for (i = n_ - 1; i > 0; i--)
pul(i);
for (h = n - 1; h >= 0; h--) {
i = get(k);
ii[h] = i;
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);
}
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
mode = 0;
memset(st, 0x3f, n_ * 2 * sizeof *st);
for (h = n - 1; h >= 0; h--) {
int h_ = query_(ii[h]);
if (h_ == INF)
root[ii[h]] = 1;
else
root[ii[h]] = 0, append(ii[h_], ii[h]);
if (ii[h] >= k - 1)
update_(ii[h] - k + 1, ii[h], h);
else
update_(0, ii[h], h), update_(ii[h] - k + 1 + n, n - 1, h);
}
for (i = 0; i < n; i++)
if (root[i])
dfs(-1, i);
mode = 1;
memset(st, 0x3f, n_ * 2 * sizeof *st);
for (i = 0; i < n; i++) {
free(ej[i]);
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
}
for (h = n - 1; h >= 0; h--) {
int h_ = query_(ii[h]);
if (h_ == INF)
root[ii[h]] = 1;
else
root[ii[h]] = 0, append(ii[h_], ii[h]);
if (ii[h] + k - 1 < n)
update_(ii[h], ii[h] + k - 1, h);
else
update_(ii[h], n - 1, h), update_(0, ii[h] + k - 1 - n, h);
}
for (i = 0; i < n; i++)
if (root[i])
dfs(-1, i);
}
int compare_plants(int x, int y) {
if (ta[0][x] <= ta[0][y] && ta[0][y] < tb[0][x] || ta[1][x] <= ta[1][y] && ta[1][y] < tb[1][x])
return 1;
if (ta[0][y] <= ta[0][x] && ta[0][x] < tb[0][y] || ta[1][y] <= ta[1][x] && ta[1][x] < tb[1][y])
return -1;
else
return 0;
}
Compilation message
plants.cpp: In function 'void append(int, int)':
plants.cpp:88:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
88 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:173:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
173 | if (ta[0][x] <= ta[0][y] && ta[0][y] < tb[0][x] || ta[1][x] <= ta[1][y] && ta[1][y] < tb[1][x])
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plants.cpp:175:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
175 | if (ta[0][y] <= ta[0][x] && ta[0][x] < tb[0][y] || ta[1][y] <= ta[1][x] && ta[1][x] < tb[1][y])
| ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
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 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
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 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
77 ms |
5160 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
