#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cassert>
using namespace std;
const int N = 1 << 18, K = 18;
// const int K = 6, N = 1 << K;
struct min_val_t {
struct node_t {
int pos, val, inc;
node_t(int _pos = 0, int _val = 0, int _inc = 0): pos(_pos), val(_val), inc(_inc) {}
} a[N << 2];
int n;
void pull(int rt) {
int lc = rt << 1, rc = lc | 1;
a[rt].pos = (a[lc].val < a[rc].val) ? a[lc].pos : a[rc].pos;
a[rt].val = min(a[lc].val, a[rc].val) + a[rt].inc;
}
void build(int rt, int lo, int hi, vector<int> &r) {
if (lo == hi) {
a[rt] = {lo, r[lo], 0};
} else {
int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
build(lc, lo, md, r);
build(rc, md + 1, hi, r);
a[rt].inc = 0;
pull(rt);
}
}
int get_val() { return a[1].val; }
int get_pos() { return a[1].pos; }
void modify(int rt, int lo, int hi, int l, int r, int x) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) {
a[rt].val += x, a[rt].inc += x;
return;
}
int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
modify(lc, lo, md, l, r, x);
modify(rc, md + 1, hi, l, r, x);
pull(rt);
}
void modify(int l, int r, int x) {
modify(1, 0, n - 1, l, r, x);
}
min_val_t(vector<int> r) {
// fprintf(stderr, "%s\n", "OK");
n = (int) r.size();
build(1, 0, n - 1, r);
}
};
struct max_dist_t {
struct node_t {
int pos, lef, rig, len, best_pos, best_dist;
node_t(int _pos = -1, int _lef = -1, int _rig = -1, int _len = 0, int _best_pos = -1, int _best_dist = -1):
pos(_pos), lef(_lef), rig(_rig), len(_len), best_pos(_best_pos), best_dist(_best_dist) {}
void on(int p) {
pos = p, lef = 0, rig = 0, len = 1, best_pos = -1, best_dist = -1;
}
void off(int p) {
pos = -1, lef = -1, rig = -1, len = 1, best_pos = -1, best_dist = -1;
}
friend node_t operator+ (node_t l, node_t r) {
node_t x;
if (l.pos == -1) x = r, x.lef += l.len, x.len += l.len;
else if (r.pos == -1) x = l, x.rig += r.len, x.len += r.len;
else {
x.pos = l.pos;
x.lef = l.lef;
x.rig = r.rig;
x.len = l.len + r.len;
if (l.best_dist > r.best_dist) {
x.best_pos = l.best_pos;
x.best_dist = l.best_dist;
} else {
x.best_pos = r.best_pos;
x.best_dist = r.best_dist;
}
if (l.rig + r.lef > x.best_dist) {
x.best_pos = r.pos;
x.best_dist = l.rig + r.lef;
}
}
return x;
}
} a[N << 1];
int n;
max_dist_t(int _n) {
n = _n;
for (int i = 0; i < N; ++i) a[N + i].off(i);
for (int i = n; i < N; ++i) a[N + i].len = 0;
for (int i = N - 1; i > 0; --i) a[i] = a[i << 1] + a[i << 1 | 1];
}
void turn_on(int i) {
a[i + N].on(i);
for (i = (i + N) / 2; i > 0; i >>= 1) a[i] = a[i << 1] + a[i << 1 | 1];
}
void turn_off(int i) {
a[i + N].off(i);
for (i = (i + N) / 2; i > 0; i >>= 1) a[i] = a[i << 1] + a[i << 1 | 1];
}
int get() {
int pos = a[1].best_pos;
// cout << "S" << a[1].pos << endl;
if (a[1].lef + a[1].rig > a[1].best_dist) pos = a[1].pos;
assert(pos != -1);
return pos;
}
};
struct assign_t {
int n, a[N << 2];
void build(int rt, int lo, int hi) {
if (lo == hi) {
a[rt] = lo;
} else {
a[rt] = -1;
int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
build(lc, lo, md);
build(rc, md + 1, hi);
}
}
assign_t(int _n) {
n = _n;
build(1, 0, n - 1);
}
void modify(int rt, int lo, int hi, int l, int r, int x) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) return a[rt] = x, void(0);
int lc = rt << 1, rc = lc | 1, md = (lo + hi) >> 1;
if (a[rt] != -1) a[lc] = a[rc] = a[rt], a[rt] = -1;
modify(lc, lo, md, l, r, x);
modify(rc, md + 1, hi, l, r, x);
}
void modify(int l, int r, int x) {
l = max(0, l), r = min(n - 1, r);
if (l <= r) modify(1, 0, n - 1, l, r, x);
}
int get(int i) {
int rt = 1, lo = 0, hi = n - 1;
while (a[rt] == -1) {
int md = (lo + hi) >> 1;
if (i <= md) rt = rt << 1, hi = md;
else rt = rt << 1 | 1, lo = md + 1;
}
return a[rt];
}
};
int n, k, init_rank[N], jump_lef[K][N], jump_rig[K][N];
int calc_dist(int l, int r) {
int d = r - l;
if (d < 0) d += n;
return d;
}
int move_idx(int i, int d) {
return (((i + d) % n) + n) % n;
}
void init(int _k, vector<int> a) {
// for (int x : a) cout << x << ' '; cout << endl;
n = (int) a.size(), k = _k;
min_val_t min_val_query(a);
max_dist_t max_dist_query(n);
assign_t assign_left_query(n), assign_right_query(n);
for (int rnk = 0; rnk < n; ++rnk) {
while (min_val_query.get_val() == 0) {
int i = min_val_query.get_pos();
max_dist_query.turn_on(i);
min_val_query.modify(i, i, N);
}
int i = max_dist_query.get();
min_val_query.modify(i - k + 1, i, -1);
min_val_query.modify(i + n - k + 1, n - 1, -1);
max_dist_query.turn_off(i);
init_rank[i] = rnk;
jump_lef[0][i] = calc_dist(assign_left_query.get(i), i);
jump_rig[0][i] = calc_dist(i, assign_right_query.get(i));
assert(move_idx(i, -jump_lef[0][i]) == move_idx(i, jump_rig[0][i]));
assign_right_query.modify(i - k + 1, i, i);
assign_right_query.modify(i + n - k + 1, n - 1, i);
assign_left_query.modify(i, i + k - 1, i);
assign_left_query.modify(0, i - n + k - 1, i);
}
for (int j = 1; j < K; ++j) {
for (int u = 0; u < n; ++u) {
int v;
v = move_idx(u, -jump_lef[j - 1][u]);
jump_lef[j][u] = jump_lef[j - 1][u] + jump_lef[j - 1][v];
v = move_idx(u, jump_rig[j - 1][u]);
jump_rig[j][u] = jump_rig[j - 1][u] + jump_rig[j - 1][v];
}
}
return;
}
bool is_shorter(int x, int y) {
// fprintf(stderr, "shorter %d %d\n", x, y);
if (x == y) return false;
int u;
u = x;
for (int j = K - 1; j >= 0; --j) {
if (jump_lef[j][u] <= calc_dist(y, u)) u = move_idx(u, -jump_lef[j][u]);
}
// fprintf(stderr, "u = %d\n", u);
if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;
u = x;
for (int j = K - 1; j >= 0; --j) {
if (jump_rig[j][u] <= calc_dist(u, y)) u = move_idx(u, jump_rig[j][u]);
}
// fprintf(stderr, "u = %d\n", u);
if ((calc_dist(u, y) < k || calc_dist(y, u) < k) && init_rank[u] >= init_rank[y]) return true;
return false;
}
int compare_plants(int x, int y) {
if (is_shorter(y, x)) return 1;
if (is_shorter(x, y)) return -1;
return 0;
}
// int main() {
// vector<int> r = {0, 1, 4, 2, 3, 6, 7, 5};
// min_val_t mv(r);
// for (int k = 0; k < 8; ++k) {
// cout << mv.get_pos() << ": " << mv.get_val() << endl;
// mv.modify(mv.get_pos(), mv.get_pos(), N * 2);
// mv.modify(0, 7, -1);
// }
// max_dist_t md(8);
// // md.turn_on(5);
// // md.turn_on(0);
// cout << md.get() << endl;
// assign_t a(8);
// cout << a.get(3) << endl;
// a.modify(1, 4, 2);
// cout << a.get(3) << endl;
// a.modify(1, 1, 3);
// cout << a.get(3) << endl;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
33276 KB |
Output is correct |
| 2 |
Runtime error |
56 ms |
67016 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33256 KB |
Output is correct |
| 2 |
Runtime error |
57 ms |
67040 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
33256 KB |
Output is correct |
| 2 |
Runtime error |
57 ms |
67040 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
67040 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
33248 KB |
Output is correct |
| 2 |
Runtime error |
57 ms |
67008 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
33256 KB |
Output is correct |
| 2 |
Runtime error |
57 ms |
67012 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
33276 KB |
Output is correct |
| 2 |
Runtime error |
56 ms |
67016 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
