#include <bits/stdc++.h>
#define ll long long
#include "plants.h"
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9;
struct seg {
int N; vector<ar<int, 2>> tree; vector<int> lazy;
void pull(int node) {
tree[node] = min(tree[node*2], tree[node*2+1]);
}
void push(int node) {
if (!lazy[node]) return;
tree[node][0] += lazy[node];
if (node < N) lazy[node*2] += lazy[node], lazy[node*2+1] += lazy[node];
lazy[node] = 0;
}
seg(int n, const vector<int>& r) : N(1<<(__lg(n)+1)), tree(2*N), lazy(2*N) {
for (int i = 0; i < n; i++) tree[i+N] = {r[i], i};
for (int i = N-1; i >= 1; i--) pull(i);
}
ar<int, 2> query(int node, int nl, int nr, int ql, int qr) {
push(node);
if (ql > nr || qr < nl) return {INF};
if (ql <= nl && nr <= qr) return tree[node];
int mid = (nl+nr)/2;
return min(query(node*2, nl, mid, ql, qr), query(node*2+1, mid+1, nr, ql, qr));
}
void update(int node, int nl, int nr, int ql, int qr, int v) {
push(node);
if (ql > nr || qr < nl) return;
if (ql <= nl && nr <= qr) {
lazy[node] += v; push(node); return;
}
int mid = (nl+nr)/2;
update(node*2, nl, mid, ql, qr, v), update(node*2+1, mid+1, nr, ql, qr, v);
pull(node);
}
};
struct seg2 {
int N; vector<ar<int, 2>> tree;
seg2(int n) : N(1<<(__lg(n)+1)), tree(2*N, {INF}) {}
void update(int pos, ar<int, 2> nw) {
for (int i = pos + N; i; i >>= 1) ckmin(tree[i], nw);
}
ar<int, 2> query(int node, int nl, int nr, int ql, int qr) {
if (ql > nr || qr < nl) return {INF};
if (ql <= nl && nr <= qr) return tree[node];
int mid = (nl+nr)/2;
return min(query(node*2, nl, mid, ql, qr), query(node*2+1, mid+1, nr, ql, qr));
}
};
const int LOG = 19;
int n, k;
vector<int> got;
vector<vector<int>> toL, toR;
int dist(int x) {
return x < 0 ? x + n : x;
}
void init(int _k, std::vector<int> r) {
k = _k;
n = sz(r);
seg st(n, r);
got.resize(n);
set<int> in;
set<ar<int, 2>> where;
auto add = [&](int pos) {
//cout << "Add " << pos << endl;
assert(!in.count(pos));
if (in.size() > 1) {
auto it = in.lower_bound(pos);
int R = it != in.end() ? *it : *in.begin();
int L = it != in.begin() ? *prev(it) : *prev(in.end());
assert(where.count({dist(R - L), R}));
where.erase({dist(R - L), R});
where.insert({dist(R - pos), R});
where.insert({dist(pos - L), pos});
}
else if (in.size() == 1) {
int other = *in.begin();
assert(where.size() == 1);
assert((*where.begin())[0] == n);
where.erase(where.begin());
where.insert({dist(other - pos), other});
where.insert({dist(pos - other), pos});
}
else {
where.insert({n, pos});
}
in.insert(pos);
};
auto rem = [&](int pos) {
//cout << "Rem " << pos << endl;
assert(in.count(pos));
if (in.size() == 1) {
in.erase(in.begin());
where.erase(where.begin());
}
else if (in.size() == 2) {
int other = *in.begin() == pos ? *next(in.begin()) : *in.begin();
assert(where.count({dist(pos - other), pos}));
in.erase(pos);
where.erase(where.begin());
where.erase(where.begin());
where.insert({n, other});
}
else {
auto it = in.upper_bound(pos);
int R = it != in.end() ? *it : *in.begin();
auto it2 = in.lower_bound(pos);
int L = it2 != in.begin() ? *prev(it2) : *prev(in.end());
assert(where.count({dist(R - pos), R}));
assert(where.count({dist(pos - L), pos}));
where.erase({dist(R - pos), R});
where.erase({dist(pos - L), pos});
where.insert({dist(R - L), R});
in.erase(pos);
}
};
int on = n;
while (1) {
auto q = st.query(1, 0, st.N-1, 0, n-1);
if (!q[0]) {
add(q[1]);
st.update(1, 0, st.N-1, q[1], q[1], INF);
}
else {
if (where.empty()) break;
auto [val, pos] = *prev(where.end());
assert(val >= k);
rem(pos);
got[pos] = on--;
int L = pos - k + 1, R = pos - 1;
if (L < 0) L += n;
if (R < 0) R += n;
if (L <= R) st.update(1, 0, st.N-1, L, R, -1);
else {
st.update(1, 0, st.N-1, 0, R, -1);
st.update(1, 0, st.N-1, L, n-1, -1);
}
}
}
toL.resize(LOG, vector<int>(2 * n, 2 * n));
toR.resize(LOG, vector<int>(2 * n, -1));
vector<int> idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int x, int y) { return got[x] > got[y]; });
seg2 st2(n);
auto query = [&](int l, int r) {
return st2.query(1, 0, st2.N-1, max(0, l), min(2*n-1, r));
};
for (int i = 0; i < n; i++) {
int pos = idx[i];
for (int d : {0, n}) {
auto l = query(pos + d - k + 1, pos + d - 1);
toL[0][pos + d] = l[0] == INF ? 2 * n : l[1];
auto r = query(pos + d + 1, pos + d + k - 1);
toR[0][pos + d] = r[0] == INF ? -1 : r[1];
st2.update(pos, ar<int, 2>{got[pos], pos});
st2.update(pos + d, ar<int, 2>{got[pos], pos + d});
}
}
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < 2 * n; j++) {
toL[i][j] = toL[i-1][j] < 2 * n ? toL[i-1][toL[i-1][j]] : 2 * n;
toR[i][j] = ~toR[i-1][j] ? toR[i-1][toR[i-1][j]] : -1;
}
}
}
bool win_left(int x, int y) {
if (x >= y) {
for (int i = LOG-1; i >= 0; i--) if (toL[i][x] < 2 * n && toL[i][x] >= y + (k - 1)) x = toL[i][x];
if (x <= y + (k - 1) && got[x] < got[y]) return 1;
x = toL[0][x];
return x < 2 * n && x >= y - (k - 1) && got[x % n] <= got[y % n];
}
else {
x += n;
for (int i = LOG-1; i >= 0; i--) if (toL[i][x] < 2 * n && toL[i][x] >= y + (k - 1)) x = toL[i][x];
if (x <= y + (k - 1) && got[x % n] < got[y]) return 1;
x = toL[0][x];
return x < 2 * n && x >= y - (k - 1) && got[x % n] <= got[y % n];
}
}
bool win_right(int x, int y) {
if (x <= y) {
for (int i = LOG-1; i >= 0; i--) if (~toR[i][x] && toR[i][x] <= y - (k - 1)) x = toR[i][x];
if (x >= y - (k - 1) && got[x] < got[y]) return 1;
x = toR[0][x];
return ~x && x <= y + k - 1 && got[x % n] <= got[y % n];
}
else {
y += n;
for (int i = LOG-1; i >= 0; i--) if (~toR[i][x] && toR[i][x] <= y - (k - 1)) x = toR[i][x];
if (x >= y - (k - 1) && got[x] < got[y]) return 1;
x = toR[0][x];
return ~x && x <= y + k - 1 && got[x % n] <= got[y % n];
}
}
bool win(int x, int y) {
return win_left(x, y) || win_right(x, y);
}
int compare_plants(int x, int y) {
int w1 = win(x, y), w2 = win(y, x);
assert(!w1 || !w2);
return !w1 && !w2 ? 0 : w1 ? -1 : 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
