| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1252148 | jerry | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include <assert.h>
#include <utility>
#include <vector>
class SegmentTree {
public:
SegmentTree(const std::vector<int>& data);
int query_max(int l, int r) const; // include-exclude
int get_next_le(int from, int value) const;
int get_prev_gt(int from, int value) const;
private:
int n;
std::vector<int> max, min;
};
class SingleSideSolver {
public:
SingleSideSolver(const std::vector<int>& _t, const std::vector<int>& _h);
bool can_reach(int l, int s, int d) const;
private:
int get_strictest_column(int l, int r) const;
int get_leftmost_reachable_column(int s, int l) const;
bool reduce_columns(const std::vector<int>& idxs) const;
const std::vector<int> t, h;
const SegmentTree row_tree, col_tree;
};
std::unique_ptr<SingleSideSolver> left, right;
int n, m;
void initialize(std::vector<int> t, std::vector<int> h) {
n = t.size();
m = h.size();
left = std::make_unique<SingleSideSolver>(t, h);
right = std::make_unique<SingleSideSolver>(t, std::vector<int>(h.rbegin(), h.rend()));
}
bool can_reach(int l, int r, int s, int d) {
return left->can_reach(l, s, d) && right->can_reach(m - r - 1, m - s - 1, m - d - 1);
}
SegmentTree::SegmentTree(const std::vector<int>& data) {
n = data.size() + 1;
while (__builtin_popcount(n) > 1)
n += n & -n;
max = std::vector<int>(n * 2, INT_MAX);
min = std::vector<int>(n * 2, INT_MIN);
for (int i = 0; i < data.size(); i++)
max[i + n] = min[i + n] = data[i];
for (int i = n - 1; i > 0; i--) {
max[i] = std::max(max[i * 2], max[i * 2 + 1]);
min[i] = std::min(min[i * 2], min[i * 2 + 1]);
}
}
int SegmentTree::query_max(int l, int r) const {
int answer = INT_MIN;
for (l += n, r += n; l != r; l /= 2, r /= 2) {
if (l & 1)
answer = std::max(answer, max[l++]);
if (r & 1)
answer = std::max(answer, max[--r]);
}
return answer;
}
int SegmentTree::get_next_le(int from, int value) const {
from += n;
while (min[from] > value) {
if (from % 2 == 0)
while (from % 2 == 0)
from /= 2;
else
from++;
}
while (from < n) {
from *= 2;
if (min[from] > value)
from++;
}
return from - n;
}
int SegmentTree::get_prev_gt(int from, int value) const {
if (query_max(0, from + 1) <= value)
return -1;
from += n;
while (max[from] <= value) {
if (from % 2 == 1)
while (from % 2 == 1)
from /= 2;
else
from--;
}
while (from < n) {
from *= 2;
if (max[from + 1] > value)
from++;
}
return from - n;
}
SingleSideSolver::SingleSideSolver(const std::vector<int>& _t, const std::vector<int>& _h)
: t(_t), h(_h), row_tree(t), col_tree(h) {}
bool SingleSideSolver::can_reach(int l, int s, int d) const {
const int col = get_leftmost_reachable_column(s, l);
const int c1 = get_strictest_column(col, s);
const int c2 = get_strictest_column(col, d);
return reduce_columns({s, c1, col, c2, d});
}
int SingleSideSolver::get_strictest_column(int l, int r) const {
return col_tree.query_max(l, r + 1);
}
int SingleSideSolver::get_leftmost_reachable_column(int s, int l) const {
int lo = l - 1, hi = s;
while (lo + 1 < hi) {
const int mid = (lo + hi) / 2;
const int c = get_strictest_column(mid, s);
if (reduce_columns({s, c, mid}))
hi = mid;
else
lo = mid;
}
return hi;
}
bool SingleSideSolver::reduce_columns(const std::vector<int>& idxs) const {
assert(t[0] > h[idxs[0]]);
int max_depth = 0;
for (int i : idxs) {
if (t[max_depth] > h[i])
max_depth = row_tree.get_next_le(max_depth, h[i]) - 1;
else
max_depth = row_tree.get_prev_gt(max_depth, h[i]);
if (max_depth < 0)
return false;
}
return true;
}