#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kLogN = 20;
class LazySegTree {
struct Node {
int val = kInf;
int dec = 0;
};
const size_t n;
vector<Node> t;
static Node unite(const Node l, const Node r) {
Node ans{};
ans.val = min(l.val, r.val);
ans.dec = 0;
return ans;
}
void push(const int x, const int l, const int r) {
assert(0 <= x and x < t.size());
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
for (const int child : {x + 1, y}) {
t[child].val -= t[x].dec;
t[child].dec += t[x].dec;
}
t[x].dec = 0;
}
void build(const int x, const int l, const int r, const vector<int> &a) {
if (l == r) {
t[x].val = a[l];
t[x].dec = 0;
return;
}
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
build(x + 1, l, mid, a);
build(y, mid + 1, r, a);
t[x] = unite(t[x + 1], t[y]);
}
int find_last_zero(const int x, const int l, const int r, const int ql, const int qr) {
if (l == r) {
return l;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
int ans = -1;
if (ql <= mid and t[x + 1].val == 0) {
ans = max(ans, find_last_zero(x + 1, l, mid, ql, qr));
}
if (mid < qr and t[y].val == 0) {
ans = max(ans, find_last_zero(y, mid + 1, r, ql, qr));
}
return ans;
}
void range_update(const int x, const int l, const int r, const int ql, const int qr) {
if (ql <= l and r <= qr) {
t[x].val--;
t[x].dec++;
return;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (ql <= mid) {
range_update(x + 1, l, mid, ql, qr);
}
if (mid < qr) {
range_update(y, mid + 1, r, ql, qr);
}
t[x] = unite(t[x + 1], t[y]);
}
void point_update(const int x, const int l, const int r, const int p, const int v) {
if (l == r) {
t[x].val = v;
t[x].dec = 0;
return;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (p <= mid) {
point_update(x + 1, l, mid, p, v);
} else {
point_update(y, mid + 1, r, p, v);
}
t[x] = unite(t[x + 1], t[y]);
}
Node query(const int x, const int l, const int r, const int ql, const int qr) {
if (ql <= l and r <= qr) {
return t[x];
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (qr <= mid) {
return query(x + 1, l, mid, ql, qr);
} else if (mid < ql) {
return query(y, mid + 1, r, ql, qr);
} else {
return unite(query(x + 1, l, mid, ql, qr),
query(y, mid + 1, r, ql, qr));
}
}
public:
explicit LazySegTree(const vector<int> &a) : n(a.size()), t(2 * n - 1) {
build(0, 0, (int) n - 1, a);
}
int find_last_zero(const int l, const int r) {
return find_last_zero(0, 0, (int) n - 1, l, r);
}
void range_update(const int l, const int r) {
range_update(0, 0, (int) n - 1, l, r);
}
void point_update(const int p, const int v) {
point_update(0, 0, (int) n - 1, p, v);
}
int query(const int l, const int r) {
return query(0, 0, (int) n - 1, l, r).val;
}
};
vector<int> find_valid_arrangement(const int k, vector<int> r) {
const int n = (int) r.size();
r.insert(r.end(), r.begin(), r.end());
vector<int> h(n, -1);
int tall = n - 1;
LazySegTree st(r);
auto point_update = [&](const int i) {
assert(n <= i and i < 2 * n);
st.point_update(i, kInf);
st.point_update(i - n, kInf);
};
auto range_update = [&](int i) {
st.range_update(i - k + 1, i);
i -= n;
const int j = i - k + 1;
st.range_update(max(0, j), i);
if (j < 0) st.range_update(2 * n + j, 2 * n - 1);
};
function<void(int)> find_height = [&](const int i) {
assert(n <= i and i < 2 * n);
while (st.query(i - k + 1, i - 1) == 0) {
const int j = st.find_last_zero(i - k + 1, i - 1);
find_height((j < n ? j + n : j));
}
h[i - n] = tall--;
point_update(i);
range_update(i);
};
while (tall >= 0) {
assert(st.query(0, 2 * n - 1) == 0);
const int i = st.find_last_zero(n, 2 * n - 1);
find_height(i);
}
return h;
}
int n = 0;
int k = 0;
vector<int> h;
vector<vector<int>> go_left;
vector<vector<int>> go_right;
void init(const int _k, vector<int> r) {
n = (int) r.size();
k = _k;
h = find_valid_arrangement(k, std::move(r));
auto dist = [&](const int i, const int j) {
return min({abs(i - j), i + n - j, j + n - i});
};
{
const auto r_ = r;
r.insert(r.end(), r_.begin(), r_.end());
r.insert(r.end(), r_.begin(), r_.end());
}
go_left.assign(n, vector<int>(kLogN));
go_right.assign(n, vector<int>(kLogN));
set<pair<int, int>> lt, rt;
lt.insert({-1, -1});
for (int i = n - k + 1; i < n; i++) {
lt.insert({h[i], i});
}
rt.insert({-1, -1});
for (int i = n + 1; i < n + k; i++) {
rt.insert({h[i % n], i});
}
for (int i = n; i < 2 * n; i++) {
const int x = i - n;
{
auto [ht, y] = *prev(lt.lower_bound(make_pair(h[x], x)));
go_left[x][0] = (y == -1 ? x : y % n);
}
{
auto [ht, y] = *prev(rt.lower_bound(make_pair(h[x], x)));
go_right[x][0] = (y == -1 ? x : y % n);
}
{
lt.erase({h[(i - k + 1) % n], i - k + 1});
rt.erase({h[(i + 1) % n], i + 1});
lt.insert({h[x], i});
rt.insert({h[(i + k) % n], i + k});
}
}
for (int i = 1; i < kLogN; i++) {
for (int x = 0; x < n; x++) {
go_left[x][i] = go_left[go_left[x][i - 1]][i - 1];
}
}
for (int i = 1; i < kLogN; i++) {
for (int x = 0; x < n; x++) {
go_right[x][i] = go_right[go_right[x][i - 1]][i - 1];
}
}
}
int dist(const int i, const int j) {
return min({abs(i - j), i + n - j, j + n - i});
}
bool can_go_left(int x, const int y) {
for (int j = 0; j < kLogN; j++) {
const int nxt = go_left[x][j];
if (nxt < y and y < x) continue;
if (x < nxt and (nxt < y or y < x)) continue;
x = nxt;
}
return (dist(x, y) < k and h[x] >= h[y]);
}
bool can_go_right(int x, const int y) {
for (int j = 0; j < kLogN; j++) {
const int nxt = go_right[x][j];
if (x < y and y < nxt) continue;
if ((y < nxt or y > x) and nxt < x) continue;
x = nxt;
}
return (dist(x, y) < k and h[x] >= h[y]);
}
bool can_go(const int s, const int t) {
return can_go_left(s, t) or can_go_right(s, t);
}
int compare_plants(int x, int y) {
if (can_go(x, y)) return 1;
if (can_go(y, x)) return -1;
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from plants.cpp:1:
plants.cpp: In member function 'void LazySegTree::push(int, int, int)':
plants.cpp:34:25: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<LazySegTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | assert(0 <= x and x < t.size());
| ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:203:8: warning: variable 'dist' set but not used [-Wunused-but-set-variable]
203 | auto dist = [&](const int i, const int j) {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
