제출 #1255722

#제출 시각아이디문제언어결과실행 시간메모리
1255722EJIC_B_KEDAXObstacles for a Llama (IOI25_obstacles)C++20
37 / 100
1270 ms129032 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 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 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...