#include <bits/stdc++.h>
#include "plants.h"
template <class T> using Vec = std::vector<T>;
constexpr int INF = 1000000000;
struct Monoid {
int min;
explicit constexpr Monoid(const int m): min(m) {}
static constexpr Monoid zero() {
return Monoid(INF);
}
constexpr Monoid operator + (const Monoid& other) const {
return Monoid(std::min(min, other.min));
}
};
struct Effector {
int add;
explicit constexpr Effector(const int a): add(a) {}
static constexpr Effector one() {
return Effector(0);
}
constexpr Effector operator * (const Effector& other) const {
return Effector(add + other.add);
}
};
constexpr Monoid operator * (const Monoid& m, const Effector& e) {
return Monoid(m.min + e.add);
}
struct Segtree {
struct Node {
Monoid mn;
Effector ef;
};
int size, log;
Vec<Node> data;
void fetch(const int k) {
assert(1 <= k and k < size);
data[k].mn = data[2 * k].mn + data[2 * k + 1].mn;
}
void apply(const int k, const Effector& e) {
assert(1 <= k and k < 2 * size);
data[k].mn = data[k].mn * e;
data[k].ef = data[k].ef * e;
}
void flush(const int k) {
assert(k < size);
assert(1 <= k);
apply(2 * k, data[k].ef);
apply(2 * k + 1, data[k].ef);
data[k].ef = Effector::one();
}
void push(const int k) {
const int lsb = __builtin_ctz(k);
const int width = 31 - __builtin_clz(k);
for (int d = width; d > lsb; --d) {
flush(k >> d);
}
}
void pull(int k) {
k >>= __builtin_ctz(k);
while (k > 1) {
k >>= 1;
fetch(k);
}
}
Segtree(const Vec<int>& vec) {
log = 0;
while ((1 << log) < (int) vec.size()) {
log += 1;
}
size = 1 << log;
data.assign(2 * size, Node{Monoid::zero(), Effector::one()});
for (int i = 0; i < (int) vec.size(); ++i) {
data[i + size].mn = Monoid(vec[i]);
}
for (int i = size - 1; i > 0; --i) {
fetch(i);
}
}
void add(int l, int r, const int x) {
l += size;
r += size;
push(l);
push(r);
const Effector e(x);
for (int l0 = l, r0 = r; l0 < r0; l0 >>= 1, r0 >>= 1) {
if (l0 & 1) apply(l0++, e);
if (r0 & 1) apply(--r0, e);
}
pull(l);
pull(r);
}
void enum_zero(Vec<int>& list) {
auto dfs = [&](auto&& dfs, const int k) {
if (data[k].mn.min != 0) {
return;
}
if (k < size) {
flush(k);
dfs(dfs, 2 * k);
dfs(dfs, 2 * k + 1);
}
else {
list.push_back(k - size);
}
};
dfs(dfs, 1);
}
void assign(int i, const int v) {
i += size;
push(i);
push(i + 1);
data[i].mn = Monoid(v);
pull(i);
pull(i + 1);
}
};
int Type;
Vec<int> restore;
void init(int k, Vec<int> r) {
if (k == 2) {
Type = 1;
} else if (2 * k > (int) r.size()) {
Type = 2;
const int n = (int) r.size();
restore.resize(n);
Segtree seg(r);
std::set<int> zero;
const auto near_l = [&](const int x) {
auto itr = zero.lower_bound(x);
return itr == zero.begin() ? *zero.rbegin() : *std::prev(itr);
};
const auto near_r = [&](const int x) {
auto itr = zero.upper_bound(x);
return itr == zero.end() ? *zero.begin() : *itr;
};
int cand = -1;
const auto dist = [&](const int l, const int r) {
return l < r ? r - l : r + n - l;
};
for (int max = n - 1; max >= 0; --max) {
Vec<int> add;
seg.enum_zero(add);
for (const auto x: add) {
seg.assign(x, INF);
zero.insert(x);
}
const auto idx = [&] {
for (const auto x: add) {
if (dist(near_l(x), x) >= k) {
return x;
}
}
return cand;
}();
restore[idx] = max;
if (idx >= k - 1) {
seg.add(idx - k + 1, idx, -1);
}
else {
seg.add(0, idx, -1);
seg.add(n - (k - idx - 1), n, -1);
}
zero.erase(idx);
cand = zero.empty() ? -1 : near_r(idx);
}
// for (const auto x: restore) {
// std::cerr << x << ' ';
// }
// std::cerr << std::endl;
}
}
int compare_plants(int x, int y) {
if (Type == 1) {
} else if (Type == 2) {
return restore[x] > restore[y] ? 1 : -1;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
