#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
class PotentialMaximum {
public:
PotentialMaximum() {}
PotentialMaximum(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
Build(1, 0, n - 1, r);
}
void UpdateIndeg(int x, int z = 1) {
int l = x + 1;
int r = x + k - 1;
while (l >= n) {
l -= n;
r -= n;
}
if (n <= r) {
Update(1, 0, n - 1, l, n - 1, 0, z);
Update(1, 0, n - 1, 0, r - n, 0, z);
} else {
Update(1, 0, n - 1, l, r, 0, z);
}
}
void UpdateRank(int x, int z) {
int l = x - k + 1;
int r = x - 1;
while (l < 0) {
l += n, r += n;
}
if (n <= r) {
Update(1, 0, n - 1, l, n - 1, z, 0);
Update(1, 0, n - 1, 0, r - n, z, 0);
} else {
Update(1, 0, n - 1, l, r, z, 0);
}
}
void Delete(int x) {
UpdateRank(x, -1);
UpdateIndeg(x, -1);
Update(1, 0, n - 1, x, x, 1e9, 1e9);
}
int Query() {
return tree[1].id;
}
private:
struct Node {
int id;
int rank;
int indeg;
int lazyrank;
int lazyindeg;
};
int n, k;
vector<Node> tree;
void Apply(int u, int r, int d) {
tree[u].rank += r;
tree[u].lazyrank += r;
tree[u].indeg += d;
tree[u].lazyindeg += d;
}
void Push(int u, int lc, int rc) {
Apply(lc, tree[u].lazyrank, tree[u].lazyindeg);
Apply(rc, tree[u].lazyrank, tree[u].lazyindeg);
tree[u].lazyrank = 0;
tree[u].lazyindeg = 0;
}
void Pull(int u, int lc, int rc) {
if (tree[lc].rank != tree[rc].rank) {
if (tree[lc].rank < tree[rc].rank) {
tree[u] = tree[lc];
} else {
tree[u] = tree[rc];
}
} else {
if (tree[lc].indeg < tree[rc].indeg) {
tree[u] = tree[lc];
} else {
tree[u] = tree[rc];
}
}
tree[u].lazyrank = 0;
tree[u].lazyindeg = 0;
}
void Build(int u, int tl, int tr, const vector<int> &r) {
if (tl == tr) {
tree[u].id = tl;
tree[u].rank = r[tl];
tree[u].indeg = 0;
tree[u].lazyrank = 0;
tree[u].lazyindeg = 0;
return;
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Build(lc, tl, md, r);
Build(rc, md + 1, tr, r);
Pull(u, lc, rc);
}
void Update(int u, int tl, int tr, int l, int r, int rank, int indeg) {
if (l > tr || tl > r || tl > tr || l > r) {
return;
}
if (l <= tl && tr <= r) {
return Apply(u, rank, indeg);
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Push(u, lc, rc);
Update(lc, tl, md, l, r, rank, indeg);
Update(rc, md + 1, tr, l, r, rank, indeg);
Pull(u, lc, rc);
}
};
class Relax {
public:
Relax() {}
Relax(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
Build(1, 0, n - 1, r);
}
void Update(int x) {
int l = x - k + 1;
int r = x - 1;
while (l < 0) {
l += n, r += n;
}
if (n <= r) {
Update(1, 0, n - 1, l, n - 1, -1);
Update(1, 0, n - 1, 0, r - n, -1);
} else {
Update(1, 0, n - 1, l, r, -1);
}
}
void Delete(int x) {
Update(1, 0, n - 1, x, x, 1e9);
}
pair<int, int> Query(int x) {
int l = x - k + 1;
int r = x - 1;
while (l < 0) {
l += n, r += n;
}
Node res;
if (n <= r) {
auto ll = Query(1, 0, n - 1, l, n - 1);
auto rr = Query(1, 0, n - 1, 0, r - n);
if (ll.rank < rr.rank) {
res = ll;
} else {
res = rr;
}
} else {
res = Query(1, 0, n - 1, l, r);
}
return {res.id, res.rank};
}
private:
struct Node {
int id;
int rank;
int lazyrank;
};
int n, k;
vector<Node> tree;
void Apply(int u, int r) {
tree[u].rank += r;
tree[u].lazyrank += r;
}
void Push(int u, int lc, int rc) {
Apply(lc, tree[u].lazyrank);
Apply(rc, tree[u].lazyrank);
tree[u].lazyrank = 0;
}
void Pull(int u, int lc, int rc) {
if (tree[lc].rank < tree[rc].rank) {
tree[u] = tree[lc];
} else {
tree[u] = tree[rc];
}
tree[u].lazyrank = 0;
}
void Build(int u, int tl, int tr, const vector<int> &r) {
if (tl == tr) {
tree[u].id = tl;
tree[u].rank = r[tl];
tree[u].lazyrank = 0;
return;
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Build(lc, tl, md, r);
Build(rc, md + 1, tr, r);
Pull(u, lc, rc);
}
void Update(int u, int tl, int tr, int l, int r, int rank) {
if (l > tr || tl > r || tl > tr || l > r) {
return;
}
if (l <= tl && tr <= r) {
return Apply(u, rank);
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Push(u, lc, rc);
Update(lc, tl, md, l, r, rank);
Update(rc, md + 1, tr, l, r, rank);
Pull(u, lc, rc);
}
Node Query(int u, int tl, int tr, int l, int r) {
if (l > tr || tl > r || tl > tr || l > r) {
return Node({-1, (int) 1e9, (int) 1e9});
}
if (l <= tl && tr <= r) {
return tree[u];
}
int md = (tl + tr) / 2;
int lc = u + 1;
int rc = u + 2 * (md - tl + 1);
Push(u, lc, rc);
auto ll = Query(lc, tl, md, l, r);
auto rr = Query(rc, md + 1, tr, l, r);
if (ll.rank < rr.rank) {
return ll;
} else {
return rr;
}
}
};
int n, k;
vector<int> h;
vector<vector<int>> next_inc;
vector<vector<int>> next_dec;
// Greedily find a valid arrangement h
// Indices i, j are comparable if |i - j| < k
// x and y are comparable if there exists a sequence
// h[x] < h[i1] < h[i2] < ... < h[y] and adjacent elements
// have distance < k.
void init(int k, vector<int> r) {
n = (int) r.size();
::k = k;
h.assign(n, -1);
{ // find a valid configuration h
Relax relax(n, k, r);
PotentialMaximum maxim(n, k, r);
for (int i = 0; i < n; i++) {
if (r[i] == 0) {
relax.Delete(i);
maxim.UpdateIndeg(i);
}
}
for (int v = n - 1; v >= 0; v--) {
int id = maxim.Query();
h[id] = v;
relax.Update(id);
maxim.Delete(id);
while (relax.Query(id).second == 0) {
int p = relax.Query(id).first;
maxim.UpdateIndeg(p);
relax.Delete(p);
}
}
}
{ // initialize binary lifting
for (int i = 0; i < n; i++) {
h.emplace_back(h[i]);
}
set<pair<int, int>> st;
next_inc.assign(20, vector<int>(2 * n, -1));
next_dec.assign(20, vector<int>(2 * n, -1));
for (int i = 2 * n - 1; i >= 0; i--) {
if (i + k < 2 * n) {
st.erase({h[i], i});
}
auto it = st.lower_bound({h[i], i});
next_inc[0][i] = it == end(st) ? -1 : it->second;
next_dec[0][i] = it == begin(st) ? -1 : prev(it)->second;
st.insert({h[i], i});
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i < 2 * n; i++) {
if (next_inc[j - 1][i] == -1) {
next_inc[j][i] = -1;
} else {
next_inc[j][i] = next_inc[j - 1][next_inc[j - 1][i]];
}
if (next_dec[j - 1][i] == -1) {
next_dec[j][i] = -1;
} else {
next_dec[j][i] = next_dec[j - 1][next_dec[j - 1][i]];
}
}
}
}
}
bool Sequence(int t, int x, int y) { // 0 = increasing, 1 = decreasing
auto &nxt = (t == 0 ? next_inc : next_dec);
for (int j = 19; j >= 0; j--) {
if (nxt[j][x] <= y) {
x = nxt[j][x];
}
}
return y - x < k;
}
int compare_plants(int x, int y) {
bool comparable = false;
if (h[x] < h[y]) {
comparable |= Sequence(0, x, y);
comparable |= Sequence(1, y, x + n);
} else {
comparable |= Sequence(0, y, x + n);
comparable |= Sequence(1, x, y);
}
return comparable ? (h[x] > h[y] ? 1 : -1) : 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
288 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
