#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
const int maxk = 20;
const int inf = 1e9 + 20;
int a[maxn];
int tree[maxn * 4];
int lazy[maxn * 4];
int step_left[maxn][maxk];
int step_right[maxn][maxk];
int height[maxn];
set<int> all_zeroes, good_zeroes;
int n, k;
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = a[lt];
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}
void update(int id, int lt, int rt, int ql, int qr, int add) {
if (lt == ql && rt == qr) {
tree[id] += add;
lazy[id] += add;
return;
}
tree[id * 2] += lazy[id];
lazy[id * 2] += lazy[id];
tree[id * 2 + 1] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) / 2;
if (qr <= mt) {
update(id * 2, lt, mt, ql, qr, add);
}
else if (ql >= mt + 1) {
update(id * 2 + 1, mt + 1, rt, ql, qr, add);
}
else {
update(id * 2, lt, mt, ql, mt, add);
update(id * 2 + 1, mt + 1, rt, mt + 1, qr, add);
}
tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}
bool contains(int x, int y) {
if (x < y) {
return y - x + 1 <= k;
}
else {
return n - (x - y - 1) <= k;
}
}
void add_zero(int x) {
auto it = all_zeroes.insert(x).first;
int prv = (it == all_zeroes.begin() ? *all_zeroes.rbegin() : *prev(it));
if (!contains(prv, x)) {
good_zeroes.insert(x);
}
int nxt = (next(it) == all_zeroes.end() ? *all_zeroes.begin() : *next(it));
if (contains(x, nxt)) {
good_zeroes.erase(nxt);
}
else {
good_zeroes.insert(nxt);
}
}
void rem_zero(int x) {
auto it = all_zeroes.find(x);
int prv = (it == all_zeroes.begin() ? *all_zeroes.rbegin() : *prev(it));
int nxt = (next(it) == all_zeroes.end() ? *all_zeroes.begin() : *next(it));
if (contains(prv, nxt)) {
good_zeroes.erase(nxt);
}
else {
good_zeroes.insert(nxt);
}
int rt = x;
int lt = (rt + n - (k - 1)) % n;
if (lt <= rt) {
update(1, 0, n - 1, lt, rt, -1);
}
else {
update(1, 0, n - 1, lt, n - 1, -1);
update(1, 0, n - 1, 0, rt, -1);
}
all_zeroes.erase(it);
good_zeroes.erase(x);
}
void find_zeroes(int id, int lt, int rt) {
if (tree[id] > 0) {
return;
}
if (lt == rt) {
add_zero(lt);
tree[id] = inf;
lazy[id] = 0;
return;
}
tree[id * 2] += lazy[id];
lazy[id * 2] += lazy[id];
tree[id * 2 + 1] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) / 2;
find_zeroes(id * 2, lt, mt);
find_zeroes(id * 2 + 1, mt + 1, rt);
tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}
int dist_right(int x, int y) {
return (y + n - x) % n;
}
int dist_left(int x, int y) {
return (x + n - y) % n;
}
void init(int _k, vector<int> _a) {
n = _a.size();
k = _k;
for (int i = 0; i < n; i++) {
a[i] = _a[i];
}
build(1, 0, n - 1);
for (int i = n - 1; i >= 0; i--) {
find_zeroes(1, 0, n - 1);
height[*good_zeroes.begin()] = i;
rem_zero(*good_zeroes.begin());
}
set<pair<int, int>> heights;
for (int i = 0; i < k - 1; i++) {
heights.emplace(height[i], i);
}
for (int i = 0; i < n; i++) {
int prv = (i + n - 1) % n;
int nxt = (i + k - 1) % n;
auto it = heights.upper_bound(make_pair(height[prv], -1));
step_right[prv][0] = (it == heights.end() ? 0 : dist_right(prv, it->second));
it = heights.upper_bound(make_pair(height[nxt], -1));
step_left[nxt][0] = (it == heights.end() ? 0 : dist_left(nxt, it->second));
heights.erase(make_pair(height[i], i));
heights.emplace(height[nxt], nxt);
}
for (int k = 1; k < maxk; k++) {
for (int i = 0; i < n; i++) {
step_right[i][k] = step_right[i][k - 1] + step_right[(i + step_right[i][k - 1]) % n][k - 1];
step_left[i][k] = step_left[i][k - 1] + step_left[(i + n - step_left[i][k - 1] % n) % n][k - 1];
}
}
return;
}
int check_left(int x, int y) {
int dist = dist_left(x, y);
for (int k = maxk - 1; k >= 0; k--) {
if (step_left[x][k] < dist) {
dist -= step_left[x][k];
x = (x + n - step_left[x][k] % n) % n;
}
}
return dist < k && height[x] < height[y];
}
int check_right(int x, int y) {
int dist = dist_right(x, y);
for (int k = maxk - 1; k >= 0; k--) {
if (step_right[x][k] < dist) {
dist -= step_right[x][k];
x = (x + step_right[x][k]) % n;
}
}
return dist < k && height[x] < height[y];
}
int compare_plants(int x, int y) {
return height[x] < height[y];
/* if (check_left(x, y) || check_right(x, y)) {
return -1;
}
else if (check_left(y, x) || check_right(y, x)) {
return 1;
}
else {
return 0;
}*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
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 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
