#include <bits/stdc++.h>
#include "plants.h"
#define left left1
#define right right1
using namespace std;
int n;
int k;
vector<int> arr;
vector<int> h;
void Set(int, int);
void genSome();
void buildLeft();
void buildRight();
void init(int k_, std::vector<int> r_) {
k = k_;
arr = r_;
n = arr.size();
genSome();
for (int i = 0; i < n; i++) {
Set(i, -h[i]);
}
buildRight();
buildLeft();
}
int cur;
vector<pair<int, int>> tree;
vector<int> mod;
void build(int v, int l, int r) {
if (l + 1 == r) {
tree[v] = {arr[l], l};
} else {
int m = (l + r) / 2;
build(2 * v + 1, l, m);
build(2 * v + 2, m, r);
tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}
}
void build() {
tree.resize(4 * n);
mod.resize(4 * n);
build(0, 0, n);
}
void push(int v, int l, int r) {
tree[v].first += mod[v];
if (l + 1 != r) {
mod[2 * v + 1] += mod[v];
mod[2 * v + 2] += mod[v];
}
mod[v] = 0;
}
pair<int, int> GetMin(int v, int l, int r, int ql, int qr) {
if (ql >= r || qr <= l) {
return {n, -1};
}
push(v, l, r);
if (ql <= l && r <= qr) {
return tree[v];
}
int m = (l + r) / 2;
return min(GetMin(2 * v + 1, l, m, ql, qr),
GetMin(2 * v + 2, m, r, ql, qr));
}
pair<int, int> GetMin(int l, int r) {
// l might be negative
if (l >= 0) {
if (r > n) {
return min(GetMin(l, n), GetMin(0, r - n));
}
return GetMin(0, 0, n, l, r);
}
return min(GetMin(0, 0, n, 0, r), GetMin(0, 0, n, n + l, n));
}
void Set(int v, int l, int r, int ind, int x) {
push(v, l, r);
if (ind < l || ind >= r)
return;
if (l + 1 == r) {
tree[v] = {x, ind};
} else {
int m = (l + r) / 2;
Set(2 * v + 1, l, m, ind, x);
Set(2 * v + 2, m, r, ind, x);
tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}
}
void Set(int ind, int x) {
Set(0, 0, n, ind, x);
}
void Add(int v, int l, int r, int ql, int qr, int x) {
push(v, l, r);
if (ql >= r || qr <= l)
return;
if (ql <= l && r <= qr) {
mod[v] = x;
push(v, l, r);
return;
}
int m = (l + r) / 2;
Add(2 * v + 1, l, m, ql, qr, x);
Add(2 * v + 2, m, r, ql, qr, x);
tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}
void Add(int l, int r, int x) {
if (l >= 0) {
return Add(0, 0, n, l, r, x);
}
Add(0, 0, n, 0, r, x);
Add(0, 0, n, n + l, n, x);
}
void rec(int ind) {
while (true) {
auto pp = GetMin(ind - k + 1, ind);
if (pp.first == 0) {
rec(pp.second);
} else {
break;
}
}
h[ind] = cur--;
Set(ind, n);
Add(ind - k + 1, ind, -1);
}
void genSome() {
h.resize(n, -1);
build();
cur = n;
while (true) {
auto pp = GetMin(0, n);
if (pp.first == 0) {
rec(pp.second);
} else {
break;
}
}
}
vector<int> left, right;
vector<vector<int>> leftb, rightb;
const int LOG = 19;
void buildRight() {
right.resize(n, n);
rightb.resize(n, vector<int> (LOG));
for (int i = 0; i < n; i++) {
int l = i + 1;
int r = l + k;
auto pp = GetMin(l, r);
if (-pp.first > h[i]) {
right[i] = (pp.second - i + n) % n;
}
}
for (int i = n - 1; i >= 0; i--) {
rightb[i][0] = right[i];
for (int j = 1; j < LOG; j++) {
rightb[i][j] = rightb[(i + rightb[i][j - 1]) % n][j - 1] + rightb[i][j - 1];
if (rightb[i][j] > n) {
rightb[i][j] = n;
}
}
}
}
void buildLeft() {
left.resize(n, n);
leftb.resize(n, vector<int> (LOG));
for (int i = 0; i < n; i++) {
int l = i - k + 1;
int r = i;
auto pp = GetMin(l, r);
if (-pp.first > h[i]) {
left[i] = (i - pp.second + n) % n;
}
}
for (int i = 0; i < n; i++) {
leftb[i][0] = left[i];
for (int j = 1; j < LOG; j++) {
leftb[i][j] = leftb[((i - leftb[i][j - 1]) % n + n) % n][j - 1] + leftb[i][j - 1];
if (leftb[i][j] > n) {
leftb[i][j] = n;
}
}
}
}
bool binupLeft(int x, int y) {
int dist = (y - x + n) % n;
for (int i = LOG - 1; i >= 0; i--) {
if (leftb[y][i] <= dist) {
dist -= leftb[y][i];
y -= leftb[y][i];
y += n;
y %= n;
}
}
return h[x] >= h[y];
}
bool binupRight(int x, int y) {
int dist = (y - x + n) % n;
for (int i = LOG - 1; i >= 0; i--) {
if (rightb[x][i] <= dist) {
dist -= rightb[x][i];
x += rightb[x][i];
x += n;
x %= n;
}
}
return h[y] >= h[x];
}
int compare_plants(int x, int y) {
if (x > y)
return -compare_plants(y, x);
if (binupLeft(x, y)) {
return 1;
}
if (binupLeft(y, x)) {
return -1;
}
if (binupRight(x, y)) {
return -1;
}
if (binupRight(y, x)) {
return 1;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
