#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/day2/debug.h"
#else
#define debug(...) void(37)
#endif
const int inf = int(1e9);
struct SegTree {
struct node {
array<int, 2> mn{};
int tag = 0;
node operator+(node x) {
node res;
res.mn = min(mn, x.mn);
return res;
}
void modify(int x) {
tag += x;
mn[0] += x;
}
};
vector<node> tree;
int n;
void push(int v, int rv) {
tree[v + 1].modify(tree[v].tag);
tree[rv].modify(tree[v].tag);
tree[v].tag = 0;
}
#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
void modify(int v, int l, int r, int ll, int rr, int x) {
debug(v, l, r, ll, rr, x);
if (l >= ll && rr >= r) {
if (l == r) {
tree[v].mn[1] = l;
}
tree[v].modify(x);
debug(v, l, r, tree[v].mn);
return;
}
def;
push(v, rv);
if (mid >= ll) {
modify(v + 1, l, mid, ll, rr, x);
}
if (mid < rr) {
modify(rv, mid + 1, r, ll, rr, x);
}
tree[v] = tree[v + 1] + tree[rv];
debug(v, l, r, tree[v].mn);
}
array<int, 2> root() {
return tree[0].mn;
}
void modify(int l, int r, int x) {
modify(0, 0, n - 1, l, r, x);
}
SegTree(int _n) : n(_n) {
tree.resize(n * 2);
}
};
int N, K, LG;
vector<int> ord;
vector<vector<int>> liftL, liftR;
void init(int _K, std::vector<int> R) {
N = int(R.size());
K = _K;
LG = __lg(N) + 1;
SegTree st(N);
for (int i = 0; i < N; ++i) {
st.modify(i, i, +R[i]);
}
debug(N, K, LG, R);
set<int> act;
set<pair<int, int>> dists;
vector<int> cur_len(N, -1);
vector<int> use;
auto Upd_len = [&](int x) {
debug("upd after", x);
if (act.empty()) {
return;
}
auto it = act.lower_bound(x);
if (it == act.begin()) {
it = act.end();
}
it = prev(it);
x = *it;
debug("upd", x);
//debug(dists);
if (cur_len[x] != -1) {
dists.erase(dists.find(pair{cur_len[x], x}));
}
it = next(it);
if (it == act.end()) {
int from = *act.begin();
cur_len[x] = from + N - x;
} else {
cur_len[x] = *it - x;
}
dists.emplace(cur_len[x], x);
};
auto Add_seg = [&](int x) {
debug("add", x);
act.insert(x);
Upd_len(x + 1);
Upd_len(x);
};
vector<int> next(N, -1);
auto Push_segs = [&](int last) {
debug(st.root());
while (st.root()[0] == 0) {
debug("add", st.root());
int id = st.root()[1];
st.modify(id, id, +inf);
next[id] = (last == -1 ? id : last);
Add_seg(id);
}
};
Push_segs(-1);
ord.resize(N);
for (int i = 0; i < N; ++i) {
debug(dists);
assert(!dists.empty());
auto it = prev(dists.end());
auto[len, id] = *it;
debug("########################", i, len, id);
ord[id] = i;
assert(len >= K);
dists.erase(it);
act.erase(id);
Upd_len(id);
int r = id + K - 1;
debug("upd seg tree");
if (r < N) {
debug(id, r);
st.modify(id, r, -1);
} else {
debug(id, N - 1);
debug(0, r);
r %= N;
st.modify(id, N - 1, -1);
st.modify(0, r, -1);
}
Push_segs(id);
}
liftL.resize(LG, vector<int>(N));
liftR.resize(LG, vector<int>(N));
set<pair<int, int>> mx;
for (int i = 1; i < K; ++i) {
mx.emplace(ord[i], i);
}
for (int i = 0; i < N; ++i) {
auto it = mx.lower_bound(pair{ord[i], -1});
liftR[0][i] = (it == mx.begin() ? i : prev(it)->second);
int add = (i + K) % N;
mx.emplace(ord[add], add);
int rem = (i + 1) % N;
mx.erase(pair{ord[rem], rem});
}
liftL[0] = next;
for (int l = 1; l < LG; ++l) {
for (int i = 0; i < N; ++i) {
liftL[l][i] = liftL[l - 1][liftL[l - 1][i]];
liftR[l][i] = liftR[l - 1][liftR[l - 1][i]];
}
}
debug(ord, next, liftR[0]);
}
bool DependsL(int x, int y) {
if (ord[x] > ord[y]) {
swap(x, y);
}
debug(x, y);
auto Between = [&](int go) {
return (x <= y ? (x < go && go <= y) : (go <= y || x < go));
};
for (int l = LG - 1; l >= 0; --l) {
int go = liftL[l][y];
if (Between(go)) {
swap(go, y);
}
}
debug(x, y);
y = liftL[0][y];
debug(y);
return !Between(y) || y == x; //replace with movability check if it gets wa
}
bool DependsR(int x, int y) {
if (ord[x] > ord[y]) {
swap(x, y);
}
debug(x, y);
auto Between = [&](int go) {
return (x >= y ? (x > go && go >= y) : (go >= y || x > go));
};
for (int l = LG - 1; l >= 0; --l) {
int go = liftR[l][y];
debug(go, Between(go));
if (Between(go)) {
swap(go, y);
}
}
y = liftR[0][y];
return !Between(y) || y == x; //replace with movability check if it gets wa
}
int compare_plants(int x, int y) {
debug("compare", x, y);
if (DependsL(x, y) || DependsR(x, y)) {
return (ord[x] < ord[y] ? 1 : -1);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
296 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
424 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
300 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
296 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
