// I can do all things through Christ who strengthens me
// Philippians 4:13
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 200005;
int n, k;
vi r;
int bad[MAXN];
bool vis[MAXN];
int h[MAXN];
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
struct SegTree {
pair<ii, int> mx[MAXN * 4];
ii lz[MAXN * 4];
void init(int u = 1, int lo = 0, int hi = n - 1) {
lz[u] = {0, 0};
if (lo == hi) {
mx[u] = {{r[lo], 0}, lo};
return;
}
MLR;
init(lc, lo, mid);
init(rc, mid + 1, hi);
mx[u] = max(mx[lc], mx[rc]);
}
void apply(ii x, int u, int lo, int hi) {
mx[u].FI.FI += x.FI;
mx[u].FI.SE += x.SE;
lz[u].FI += x.FI;
lz[u].SE += x.SE;
}
void propo(int u, int lo, int hi) {
if (lz[u] == ii(0, 0)) {
return;
}
MLR;
apply(lz[u], lc, lo, mid);
apply(lz[u], rc, mid + 1, hi);
lz[u] = {0, 0};
}
void incre(int s, int e, ii x, int u = 1, int lo = 0, int hi = n - 1) {
if (s >= n) {
incre(s - n, e - n, x);
return;
}
if (e >= n) {
incre(s, n - 1, x);
incre(0, e - n, x);
return;
}
if (lo >= s && hi <= e) {
apply(x, u, lo, hi);
return;
}
MLR;
propo(u, lo, hi);
if (s <= mid) {
incre(s, e, x, lc, lo, mid);
}
if (e > mid) {
incre(s, e, x, rc, mid + 1, hi);
}
mx[u] = max(mx[lc], mx[rc]);
}
pair<ii, int> qmx(int s, int e, int u = 1, int lo = 0, int hi = n - 1) {
if (s >= n) {
return qmx(s - n, e - n);
}
if (e >= n) {
return max(qmx(s, n - 1), qmx(0, e - n));
}
if (lo >= s && hi <= e) {
return mx[u];
}
MLR;
propo(u, lo, hi);
pair<ii, int> res = {{-INF, -INF}, -INF};
if (s <= mid) {
mxto(res, qmx(s, e, lc, lo, mid));
}
if (e > mid) {
mxto(res, qmx(s, e, rc, mid + 1, hi));
}
return res;
}
} st1, st2;
int p[MAXN], rnk[MAXN];
void init() {
REP (i, 0, n) {
p[i] = i;
rnk[i] = 0;
}
}
int findp(int i) {
if (p[i] == i) {
return i;
}
return p[i] = findp(p[i]);
}
bool join(int a, int b) {
int pa = findp(a), pb = findp(b);
if (pa == pb) {
return 0;
}
if (rnk[pa] < rnk[pb]) {
swap(pa, pb);
}
if (rnk[pa] == rnk[pb]) {
rnk[pa]++;
}
p[pb] = pa;
return 1;
}
void init(int _k, vi _r) {
k = _k; r = _r;
n = SZ(r);
st1.init();
st2.init();
init();
REP (i, 0, n) {
if (r[i] == k - 1) {
st1.incre(i + 1, i + k - 1, {0, -1});
st2.incre(i, i, {-INF, -INF});
REP (j, i + 1, i + k) {
join(i, j % n);
}
}
}
int z = 1;
while (1) {
vi todo;
while (1) {
auto [tmp, id] = st1.qmx(0, n - 1);
if (tmp != ii(k - 1, 0)) {
break;
}
cerr << id << ' ' << z << '\n';
h[id] = z;
st1.incre(id, id, {-INF, -INF});
todo.pb(id);
}
if (todo.empty()) {
break;
}
for (int id : todo) {
st1.incre(id + 1, id + k - 1, {0, 1});
st1.incre(id - k + 1 + n, id - 1 + n, {1, 0});
st2.incre(id - k + 1 + n, id - 1 + n, {1, 0});
auto [v, u] = st2.qmx(id - k + 1 + n, id - 1 + n);
while (v.FI == k - 1) {
st1.incre(u + 1, u + k - 1, {0, -1});
st2.incre(u, u, {-INF, -INF});
tie(v, u) = st2.qmx(id - k + 1 + n, id - 1 + n);
}
}
z++;
}
return;
}
int compare_plants(int x, int y) {
if (findp(x) != findp(y)) {
if ((x + 1) % n == y) {
return -1;
}
if ((y + 1) % n == x) {
return 1;
}
return 0;
} else if (h[x] > h[y]) {
return 1;
} else {
return -1;
}
}
Compilation message
plants.cpp: In member function 'void SegTree::init(int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
plants.cpp:55:9: note: in expansion of macro 'MLR'
55 | MLR;
| ^~~
plants.cpp: In member function 'void SegTree::propo(int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
plants.cpp:70:9: note: in expansion of macro 'MLR'
70 | MLR;
| ^~~
plants.cpp: In member function 'void SegTree::incre(int, int, ii, int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
plants.cpp:89:9: note: in expansion of macro 'MLR'
89 | MLR;
| ^~~
plants.cpp: In member function 'std::pair<std::pair<int, int>, int> SegTree::qmx(int, int, int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
plants.cpp:109:9: note: in expansion of macro 'MLR'
109 | MLR;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
388 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
