#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniq(x) x.resize(unique(all(x)) - x.begin()) #define sort_uniq(x) sort(all(x)), uniq(x) #define no_el(x, y) x.find(y) == x.end() #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define V vector #define pb push_back #define eb emplace_back #define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define INF INT32_MAX #define blt __builtin_popcount #define sz(x) int(x.size()) #define rep(a, b, c, d) for (int a = b; a <= c; a += d) #define repl(a, b, c, d) for (int a = b; a >= c; a -= d) #define ld long double mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count()); const int N = 8e5 + 5; const int LG = 19; int n, m; V<int> t, h; int stmn[N][LG], stmx[N][LG], lg2[N]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int p[N]; V<int> comp[N]; void mrg(int a, int b) { a = p[a], b = p[b]; if (a == b) return; if (sz(comp[a]) < sz(comp[b])) swap(a, b); for (auto i : comp[b]) { comp[a].pb(i); p[i] = a; } } void initialize(std::vector<int> T, std::vector<int> H) { n = sz(T), m = sz(H); t.resize(n + 1), h.resize(m + 1); rep(i, 1, n, 1) t[i] = T[i - 1]; rep(i, 1, m, 1) h[i] = H[i - 1]; rep(i, 1, m, 1) { stmn[i][0] = h[i]; stmx[i][0] = h[i]; } rep(j, 1, LG - 1, 1) { rep(i, 1, m, 1) { int nx = i + (1 << (j - 1)); if (nx <= m) { stmn[i][j] = min(stmn[i][j - 1], stmn[nx][j - 1]); stmx[i][j] = max(stmx[i][j - 1], stmx[nx][j - 1]); } else { stmn[i][j] = stmn[i][j - 1]; stmx[i][j] = stmx[i][j - 1]; } } } lg2[1] = 0; rep(i, 2, N - 1, 1) { lg2[i] = lg2[i >> 1] + 1; } rep(i, 1, N - 1, 1) { p[i] = i; comp[i] = {i}; } rep(i, 1, n, 1) { rep(j, 1, m, 1) { if (t[i] <= h[j]) continue; rep(it, 0, 3, 1) { int nxx = i + dx[it]; if (nxx < 1 || nxx > n) continue; int nxy = j + dy[it]; if (nxy < 1 || nxy > m) continue; if (t[nxx] > h[nxy]) { mrg((nxx - 1) * m + nxy, (i - 1) * m + j); //cout << i << " " << j << " " << nxx << " " << nxy << "\n"; } } } } } int min_rng(int l, int r) { int j = lg2[r - l + 1]; return min(stmn[l][j], stmn[r - (1 << j) + 1][j]); } int max_rng(int l, int r) { int j = lg2[r - l + 1]; return max(stmx[l][j], stmx[r - (1 << j) + 1][j]); } bool can_reach1(int l, int r, int s, int d) { ++s; ++d; if (p[s] == p[d]) return true; return false; } bool can_reach2(int l, int r, int s, int d) { ++s; ++d; if (s > d) swap(s, d); //if (max_rng(s, d) < t[1]) return true; //return false; l = 1, r = s - 1; int lb = s, rb = s, ans = s; rep(i, 1, n, 1) { int l = 1, r = lb - 1, ans = lb; while (l <= r) { int md = l + r >> 1; if (max_rng(md, s) < t[i]) { r = md - 1; ans = md; } else l = md + 1; } lb = ans; l = rb + 1, r = m, ans = rb; while (l <= r) { int md = l + r >> 1; if (max_rng(s, md) < t[i]) { l = md + 1; ans = md; } else r = md - 1; } rb = ans; if (rb >= d) return true; if (i == n) return false; if (t[i + 1] <= min_rng(lb, rb)) return false; } return false; } bool can_reach(int l, int r, int s, int d) { if (can_reach1(l, r, s, d) != can_reach2(l, r, s, d)) { rep(i, 1, m, 1) cout << h[i] << endl; assert(false); } return can_reach1(l, r, s, d); }