| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1255735 | EJIC_B_KEDAX | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
struct rmq {
vector<pair<int, int>> st;
size_t sz;
rmq() = default;
rmq(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz, make_pair(0, -1));
for (int i = 0; i < a.size(); i++) {
st[i + sz] = {a[i], i};
}
for (int i = sz - 1; i > 0; i--) {
st[i] = min(st[2 * i], st[2 * i + 1]);
}
}
pair<int, int> get(int l, int r) {
l += sz; r += sz;
pair<int, int> res = {INT32_MAX, -1};
while (l <= r) {
if (l & 1) {
res = min(res, st[l++]);
}
if (~r & 1) {
res = min(res, st[r--]);
}
l >>= 1;
r >>= 1;
}
return res;
}
};
vector<int> ord;
struct forest {
vector<int> d;
vector<vector<int>> binup, binupx, binupn;
int timer;
void add_vertice(int idx, int p) {
// cout << "! " << idx << ' ' << p << '\n';
ord[idx] = timer;
if (p == -1) {
d[idx] = 0;
for (int l = 0; l < binup.size(); l++) {
binup[l][idx] = idx;
binupx[l][idx] = idx;
binupn[l][idx] = idx;
}
return;
}
d[idx] = d[p] + 1;
binup[0][idx] = p;
binupx[0][idx] = max(p, idx);
binupn[0][idx] = min(p, idx);
for (int l = 1; l < binup.size(); l++) {
binup[l][idx] = binup[l - 1][binup[l - 1][idx]];
binupx[l][idx] = max(binupx[l - 1][binup[l - 1][idx]], binupx[l - 1][idx]);
binupn[l][idx] = min(binupn[l - 1][binup[l - 1][idx]], binupn[l - 1][idx]);
}
}
int up(int idx, int l1, int r1) {
int ans = idx;
int res = idx;
for (int l = binup.size() - 1; l >= 0; l--) {
if (binupn[l][res] >= l1 && binupx[l][res] <= r1) {
ans = min(ans, binupn[l][res]);
res = binup[l][res];
}
}
return ans;
}
int upr(int idx, int l1, int r1) {
int res = idx;
for (int l = binup.size() - 1; l >= 0; l--) {
if (binupn[l][res] >= l1 && binupx[l][res] <= r1) {
res = binup[l][res];
}
}
return res;
}
pair<int, int> up(int idx, int amount) {
pair<int, int> res = {idx, idx};
for (int l = binup.size() - 1; l >= 0; l--) {
if (amount & (1 << l)) {
res.second = max(res.second, binupx[l][res.first]);
res.first = binup[l][res.first];
}
}
return res;
}
forest() = default;
forest(vector<int> t, vector<int> h) {
d.resize(h.size());
ord.resize(h.size());
timer = 0;
binup.resize(20);
binupx.resize(20);
binupn.resize(20);
for (int i = 0; i < binup.size(); i++) {
binup[i].resize(h.size());
binupx[i].resize(h.size());
binupn[i].resize(h.size());
}
int cur = t.size();
int now = 0;
rmq tmin(t), tmax;
{
vector<int> tmp = t;
for (int i = 0; i < tmp.size(); i++) {
tmp[i] *= -1;
}
tmax = rmq(tmp);
}
vector<pair<int, int>> sh;
for (int i = 0; i < h.size(); i++) {
sh.emplace_back(h[i], i);
}
ranges::sort(sh);
int ptr = 0, ptr2 = sh.size() - 1;
set<int> closed, open;
while (cur > 0) {
// cout << "! " << cur << endl;
int next = -1;
if (!now) {
next = tmax.get(0, cur - 1).second;
int val = t[next];
while (ptr2 >= 0 && sh[ptr2].first >= val) {
closed.insert(sh[ptr2--].second);
}
}
if (now || next == 0) {
if (next == -1) {
next = tmin.get(0, cur - 1).second;
}
vector<int> nw;
int val = t[next];
while (ptr < sh.size() && sh[ptr].first < val) {
nw.push_back(sh[ptr++].second);
}
ranges::sort(nw);
for (int i : nw) {
auto sptr = open.lower_bound(i);
bool ok = true;
if (sptr == open.begin()) {
ok = false;
} else {
sptr--;
int free = *sptr;
auto sptr2 = closed.lower_bound(free);
if (sptr2 != closed.end() && *sptr2 <= i) {
ok = false;
}
}
if (ok) {
add_vertice(i, *sptr);
} else {
sptr = open.lower_bound(i);
ok = true;
if (sptr == open.end()) {
ok = false;
} else {
int free = *sptr;
auto sptr2 = closed.lower_bound(i);
if (sptr2 != closed.end() && *sptr2 <= free) {
ok = false;
}
}
if (ok) {
add_vertice(i, *sptr);
} else {
add_vertice(i, -1);
}
}
open.insert(i);
}
}
now = 1 - now;
cur = next;
timer++;
}
for (int i = 0; i < h.size(); i++) {
if (open.find(i) == open.end()) {
add_vertice(i, -1);
}
}
}
};
forest l_forest, r_forest;
rmq hmin;
int n;
void initialize(vector<int> t, vector<int> h) {
l_forest = forest(t, h);
hmin = rmq(h);
ranges::reverse(h);
r_forest = forest(t, h);
n = h.size();
}
bool can_reach(int L, int R, int S, int D) {
if (S > D) swap(S, D);
int lll = l_forest.upr(D, L, R);
int rrr = l_forest.upr(S, L, R);
if (lll == rrr) return true;
int m = hmin.get(S, D).second;
int ds = r_forest.d[n - 1 - S];
int dd = l_forest.d[D];
int dmr = r_forest.d[n - 1 - m];
int dml = l_forest.d[m];
auto [rv, rb] = r_forest.up(n - 1 - S, ds - dmr);
auto [lv, lb] = l_forest.up(D, dd - dml);
if (rv == n - 1 - m && lv == m && lb <= R && rb <= n - 1 - L) return true;
int lll = l_forest.up(D, L, R);
int rrr = r_forest.up(n - 1 - S, n - 1 - R, n - 1 - L);
if (n - 1 - rrr >= D && lll <= S) return true;
return false;
}