#include "obstacles.h" #include<bits/stdc++.h> #define ll long long using namespace std; // T[i] > H[i] means no obstacle, T[i] <= H[i] means obstacle // Note: N is #columns, M is #rows, reversed from problem statement ll N, M, logN = 23; vector<ll> T, H; struct plist { ll v; plist *r; plist (ll gay) { v = gay; r = nullptr; } }; struct pvec { plist *l, *r; pvec (){ l = r = nullptr; } }; struct snode { ll l, r, vi, va; snode *lc, *rc; void construct(vector<ll> &gay) { if (l == r) { vi = va = gay[l]; return; } lc = (snode*)(malloc(sizeof(snode))); rc = (snode*)(malloc(sizeof(snode))); lc -> l = l; rc -> r = r; lc -> r = floor((l+r)/2.0); rc -> l = lc -> r + 1; lc -> construct(gay); rc -> construct(gay); vi = min(lc -> vi, rc -> vi); va = max(lc -> va, rc -> va); } ll qmin(ll li, ll ri){ if (li == l && ri == r) return vi; ll output = 1e18; if (li <= lc -> r) output = lc -> qmin(li, min(ri, lc -> r)); if (ri >= rc -> l) output = min(output, rc -> qmin(max(li, rc -> l), ri)); return output; } ll qmax(ll li, ll ri){ if (li == l && ri == r) return va; ll output = -1e18; if (li <= lc -> r) output = lc -> qmax(li, min(ri, lc -> r)); if (ri >= rc -> l) output = max(output, rc -> qmax(max(li, rc -> l), ri)); return output; } pvec* qhum(ll li, ll ri, ll val){ // returns a sorted linked list on postions >= val pvec *out; out = (pvec*)(malloc(sizeof(pvec))); if (va < val) { out -> l = out -> r = nullptr; return out; } if (l == r) { out -> l = out -> r = (plist*)(malloc(sizeof(plist))); out -> l -> v = li; out -> r -> r = nullptr; return out; } if (li <= lc -> r) { free(out); out = lc -> qhum(li, min(lc -> r, ri), val); if (ri >= rc -> l){ if (out -> l == nullptr) { free(out); return rc -> qhum(max(li, rc -> l), ri, val); } auto p = rc -> qhum(max(li, rc -> l), ri, val); out -> r -> r = p -> l; if (p -> l != nullptr) out -> r = p -> r; free(p); } return out; } else { free(out); return rc -> qhum(li, ri, val); } } ll qtemp(ll li, ll ri, ll val) { // find the first position > val, or return -69 if (l == r) { if (va <= val) return -69; else return l; } if (va <= val) return -69; ll output = -69; if (li <= lc -> r) output = lc -> qtemp(li, min(ri, lc -> r), val); if (output == -69){ if (ri >= rc -> l) output = rc -> qtemp(max(li, rc -> l), ri, val); } return output; } ll qhl(ll li, ll ri, ll val) { // find the first position < val, or return -69 if (l == r) { if (vi >= val) return -69; else return l; } if (vi >= val) return -69; ll output = -69; if (li <= lc -> r) output = lc -> qhl(li, min(ri, lc -> r), val); if (output == -69){ if (ri >= rc -> l) output = rc -> qhl(max(li, rc -> l), ri, val); } return output; } ll qhr(ll li, ll ri, ll val) { // find the last position < val, or return -69 if (l == r) { if (vi >= val) return -69; else return l; } if (vi >= val) return -69; ll output = -69; if (ri >= rc -> l) output = rc -> qhr(max(li, rc -> l), ri, val); if (output == -69){ if (li <= lc -> r) output = lc -> qhr(li, min(ri, lc -> r), val); } return output; } }; snode rootn, rootm; class tnode; struct Lca { // To pass, left <= l, right >= r tnode *pos; ll l, r; Lca(){} Lca (Lca a, Lca b){ // Combines ancestor to descendent l = min(a.l, b.l); r = max(a.r, b.r); pos = a.pos; } Lca (tnode *a, ll b, ll c){ // Make a boring object lol pos = a; l = b; r = c; } }; ll adjust (ll a, ll b) { if (a == -69) return b; return a; } struct tnode{ ll l, r,h, th, pl, pr; // l, r for range, h for y value, th for tree height, //pl pr for Lca object parent pointer vector<tnode*> ch; // list of children pointers vector<Lca> lca; // LCA construct tnode *par; // parent pointer void build (vector<tnode*> &Lea, bool _indicator = true) { // do the LCA shit here ch = vector<tnode*>(0); if (_indicator) { lca = vector<Lca>(0); lca = vector<Lca> (logN); lca[0] = Lca(par, pl, pr); for (ll i = 1; i < logN; i++) { lca[i] = Lca(lca[i-1].pos -> lca[i-1], lca[i-1]); } } if (h == 0) { for (ll i = l; i <= r; i++) Lea[i] = this; return; } ll Ta = rootm.qmax(0, h-1); pvec *X = rootn.qhum(l, r, Ta); plist *lll, *rrr; lll = (plist*)(malloc(sizeof(plist))); rrr = (plist*)(malloc(sizeof(plist))); *lll = plist(l-1); *rrr = plist(r + 1); lll -> r = X -> l; X -> l = lll; if (X -> r == nullptr) X -> r = lll; X -> r -> r = rrr; X -> r = rrr; for (plist *i = X -> l; i -> r != nullptr; i = i -> r){ if (i -> r -> v - i -> v <= 1) continue; ch.push_back((tnode*)(malloc(sizeof(tnode)))); ch.back() -> l = i -> v + 1; ch.back() -> r = i -> r -> v - 1; ch.back() -> th = th + 1; ch.back() -> par = this; // now find height, pl, pr ll pe = rootn.qmax(ch.back() -> l, ch.back() -> r); ch.back() -> h = rootm.qtemp(0, h - 1, pe); pe = rootm.qmin(ch.back() -> h, h - 1); if (_indicator){ ch.back() -> pl = rootn.qhr(ch.back() -> l, ch.back() -> r, pe); ch.back() -> pr = adjust(rootn.qhl(ch.back() -> l, ch.back() -> r, pe), N+M+5); } else { ch.back() -> pl = -69; ch.back() -> pr = N+M+5; } ch.back() -> build(Lea); } } }; Lca trace(tnode *a, tnode *b){ if (a -> th < b -> th) { auto c = a; a = b; b = c; } Lca A(a, N+1, -1), B(b, N+1, -1); for (ll i = logN-1; i >= 0; i--){ if (a -> lca[i].pos -> th >= b -> th){ A = Lca(a -> lca[i], A); a = A.pos; } } if (a != b) { for (ll i = logN-1; i >= 0; i--){ if (a -> lca[i].pos != b -> lca[i].pos){ A = Lca(a -> lca[i], A); a = A.pos; B = Lca(b -> lca[i], B); b = B.pos; } } A = Lca(a -> lca[0], A); a = A.pos; B = Lca(b -> lca[0], B); b = B.pos; } A = Lca(A, B); return A; } vector<tnode*> Leaf; tnode gayroot; void initialize(std::vector<int> t, std::vector<int> h) { N = h.size(); M = t.size(); T = vector<ll>(M); H = vector<ll>(N); Leaf = vector<tnode*> (N, nullptr); for (ll i = 0; i < N; i++) H[i] = h[i]; for (ll i = 0; i < M; i++) T[i] = t[i]; rootn.l = rootm.l = 0; rootn.r = N-1; rootm.r = M-1; rootn.construct(H); rootm.construct(T); gayroot.l = 0; gayroot.r = N-1; gayroot.lca = vector<Lca>(logN, Lca(&gayroot, N+1, -1)); gayroot.pl = -1; gayroot.pr = N; gayroot.h = M; gayroot.th = 0; gayroot.build(Leaf, false); return; } bool can_reach(int L, int R, int S, int D) { ll l = L, r = R, a = S, b = D; if (Leaf[a] == nullptr || Leaf[b] == nullptr) return false; //return Leaf[a] == Leaf[b]; auto P = trace(Leaf[a], Leaf[b]); return (l <= P.l) && (r >= P.r); }