| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1320427 | MunkhErdene | Obstacles for a Llama (IOI25_obstacles) | C++17 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Global variables to store problem data
int N, M, Q_val;
vector<int> T, H;
// Sparse Table for Range Minimum Query on T
vector<vector<int>> st;
vector<int> logs;
void build_sparse_table() {
logs.resize(N + 1);
logs[1] = 0;
for (int i = 2; i <= N; i++)
logs[i] = logs[i/2] + 1;
int K = logs[N];
st.assign(N, vector<int>(K + 1));
for (int i = 0; i < N; i++)
st[i][0] = T[i];
for (int j = 1; j <= K; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}
}
}
int query_min_T(int L, int R) {
if (L > R) return 2e9; // Should not happen based on logic
int j = logs[R - L + 1];
return min(st[L][j], st[R - (1 << j) + 1][j]);
}
// DSU Structures
struct DSU {
vector<int> parent;
vector<int> min_h; // Minimum humidity in this component
vector<bool> is_dead; // True if this component is blocked from going higher
vector<vector<int>> queries; // Indices of queries pending in this component
DSU(int m, const vector<int>& h_arr) {
parent.resize(m);
min_h = h_arr;
is_dead.assign(m, false);
queries.resize(m);
for(int i=0; i<m; ++i) parent[i] = i;
}
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}
// Returns the root of the merged set
int unite(int i, int j, vector<int>& ans, const vector<pair<int, int>>& query_ends) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
// Merge smaller to larger (heuristic) for query movement
if (queries[root_i].size() > queries[root_j].size()) {
swap(root_i, root_j);
}
parent[root_i] = root_j;
min_h[root_j] = min(min_h[root_i], min_h[root_j]);
// If either was dead, the merged component is dead (it contains a trapped part)
// Actually, if one part is dead, it implies connectivity to start is broken for that part.
// If S is in a dead part and D in a live part, they merge -> whole thing is dead relative to "higher" goals?
// Actually, for the purpose of S reaching D:
// If they meet now, we just check if the resulting component is dead from *below*.
is_dead[root_j] = is_dead[root_i] || is_dead[root_j];
// Process queries from the smaller set
for (int q_idx : queries[root_i]) {
int u = query_ends[q_idx].first;
int v = query_ends[q_idx].second;
// If the other end is in the new root, we found a path!
if (find(u) == find(v)) {
// Answer is 1 if not dead, 0 if dead
ans[q_idx] = (is_dead[root_j] ? 0 : 1);
} else {
queries[root_j].push_back(q_idx);
}
}
queries[root_i].clear(); // Free memory
return root_j;
}
return root_i;
}
};
void initialize(vector<int> T_in, vector<int> H_in) {
T = T_in;
H = H_in;
N = T.size();
M = H.size();
build_sparse_table();
}
bool can_reach(int L, int R, int S, int D) {
// This function is required by the interface but for Subtask 5
// we usually solve offline or map logic.
// However, the grader calls this Q times.
// To solve Subtask 5 efficiently within the structure, we'll implement
// the batch processing logic in a way that stores answers and returns them.
// But standard competitive programming graders usually allow global state.
// We will accumulate queries and solve them all at once?
// No, standard interactive/grader problems might not allow "accumulate and solve at end".
// BUT, typical IOI style allow us to perform the logic in initialize if possible,
// or we assume can_reach is called sequentially.
// Given the constraints and problem type, usually we must answer online OR
// since L=0, R=M-1 is fixed, we can precompute everything in Initialize.
return false; // Placeholder, real logic below
}
// Global storage for queries to process in batch if necessary,
// OR we assume we can rewrite the solution to fit the grader.
// For this problem specifically, we can pre-calculate the "Connectivity Graph"
// in initialize and answer queries O(1) or O(log N).
// We will use the LCA approach on the reachability tree.
// Reachability Tree Implementation
struct Node {
int id;
int barrier_level; // The step at which this node merges into parent
bool dead;
};
vector<vector<int>> adj;
vector<int> node_depth;
vector<vector<int>> up; // Binary lifting
vector<bool> node_dead;
vector<int> leaf_mapping; // Maps column index to leaf node
int current_nodes = 0;
void build_reachability_tree() {
// Landmarks: 0 = m_k < ... < m_0
// We actually iterate from index 0 upwards in T? No.
// We identify landmarks starting from Global Max.
// But the DSU construction goes from Bottom (Row 0) to Top.
// 1. Find landmarks
vector<int> landmarks;
int curr = 0;
while (true) {
landmarks.push_back(curr);
// Find max in [0, curr - 1] ? No.
// We are going UP the rows from 0.
// Actually, the structure is: 0 is a leaf.
// We need the next row index 'm' such that T[m] > T[curr] and m is "useful"?
// No, the landmarks are defined by: m_next = index of Max T in [0, m_curr - 1] is wrong direction.
// Correct direction: m_0 = Max(0..N-1), m_1 = Max(0..m_0-1), ...
// So landmarks are computed Top-Down.
if (curr == 0) break; // We handled 0? No wait.
// This is confusing. Let's restart landmark finding.
}
landmarks.clear();
// We need the sequence: 0 = r_0, r_1, ..., r_k
// where r_i is the row index, and we move towards rows with higher reachability (Higher T).
// Actually, T[0] is the start.
// The "Bottleneck" logic dictates we care about walls.
// Walls are determined by rows with Max T.
// Let's use the explicit recursion sequence:
// Seq: 0. Then max in 0..N-1? No.
// Seq: m_0 = argmax(0..N-1), m_1 = argmax(0..m_0-1), ... m_k = 0.
// This gives us landmarks sorted by index: m_k=0 < ... < m_0.
// T values: T[m_k] <= T[m_{k-1}] ... <= T[m_0]. (Actually not strictly, but generally T increases as we widen scope).
int limit = N;
vector<int> seq;
while (limit > 0) {
// Find max T in [0, limit-1]
// We need argmax. Sparse table stores values.
// Simple linear scan is too slow O(N^2).
// Use Segment Tree or coordinate compression + RMQ?
// Or just realize we only need "Rightmost Max" to properly emulate the recursion.
// We can do this in O(N) using a monotonic stack or precalc.
// Actually, we can assume O(N) is fine.
// But simply: We need index of max in [0, R].
// This can be done with a standard segment tree or RMQ with index.
break; // Implementation detail inside initialize
}
}
// Combined Solver Class
class Solver {
vector<int> ans;
vector<pair<int, int>> queries;
// We need to map the grader calls.
// Since initialize is called once and then can_reach,
// we will buffer queries? No, can_reach must return immediately.
// This implies we MUST precompute.
// Precomputation strategy:
// Build the "Tree of Components" (Reachability Tree).
// Leaves are columns 0..M-1 at Row 0.
// Internal nodes represent merged components at higher T levels.
// Each node tracks if it is "Dead" (cut off from rising).
// Query(S, D) is:
// 1. Find leaves for S and D.
// 2. Find LCA in the tree.
// 3. If LCA is not marked "Dead" (and path to it is valid? DSU implies validity), return True.
struct TreeNode {
int parent = -1;
bool is_dead = false;
};
vector<TreeNode> tree;
vector<int> col_to_node; // Map current column set to tree node
vector<int> dsu_parent;
int find_set(int v) {
if (v == dsu_parent[v]) return v;
return dsu_parent[v] = find_set(dsu_parent[v]);
}
public:
void solve(int n, int m, const vector<int>& t, const vector<int>& h) {
// 1. Identify Landmarks (indices m_k=0 to m_0)
// Helper to get argmax in range [0, r]
// Since we repeatedly query [0, r], we can precompute prefix max indices.
// Let pm[i] be index of max T in 0...i.
// If multiple maxes, pick the largest index (closest to barrier).
vector<int> landmarks;
int curr = N - 1;
while (true) {
// Find rightmost max in 0...curr
// We can do a linear scan? No.
// But max in 0..curr is can be found via RMQ.
// Let's implement simple RMQ with Index.
int best_idx = -1;
int max_val = -1;
// Optimization: We don't need arbitrary RMQ.
// Just landmarks.
// We can iterate.
break;
}
// BETTER WAY for landmarks:
// Use a Cartesian-tree like stack construction.
// But simple recursion logic:
// m_0 = index of max in 0..N-1.
// m_1 = index of max in 0..m_0-1.
// ...
// This is O(N) if we precalc.
vector<pair<int, int>> t_indexed(N);
for(int i=0; i<N; ++i) t_indexed[i] = {T[i], i};
// Build Sparse Table for (Value, Index)
int K = 0; while((1<<(K+1)) <= N) K++;
vector<vector<pair<int, int>>> st_idx(N, vector<pair<int, int>>(K+1));
for(int i=0; i<N; ++i) st_idx[i][0] = {T[i], i}; // Prefer larger index for ties?
// Tie-breaking: If values equal, we want the one that appears later?
// Actually, if T[i] == T[j] and i < j.
// The max is T[j].
// If we pick i, then j is in i+1..R.
// But j has same height.
// It doesn't strictly matter for correctness, but consistent tie-breaking is good.
// Let's use value. If value same, pick larger index.
for(int j=1; j<=K; ++j) {
for(int i=0; i + (1<<j) <= N; ++i) {
pair<int, int> p1 = st_idx[i][j-1];
pair<int, int> p2 = st_idx[i + (1<<(j-1))][j-1];
if (p2.first >= p1.first) st_idx[i][j] = p2; // Prefer right
else st_idx[i][j] = p1;
}
}
auto get_max_idx = [&](int r) {
int k = 0; while((1<<(k+1)) <= r+1) k++;
pair<int, int> p1 = st_idx[0][k];
pair<int, int> p2 = st_idx[r - (1<<k) + 1][k];
return (p2.first >= p1.first) ? p2.second : p1.second;
};
landmarks.clear();
int r = N - 1;
while (true) {
int idx = get_max_idx(r);
landmarks.push_back(idx);
if (idx == 0) break;
r = idx - 1;
}
reverse(landmarks.begin(), landmarks.end());
// Now landmarks is 0 = m_0, m_1, ..., m_k (global max)
// 2. DSU Initialization
dsu_parent.resize(M);
col_to_node.resize(M);
vector<int> min_h(M);
// Tree starts with leaves.
// However, some columns might be dead immediately at row 0?
// (i.e. H[c] >= T[0]).
// But problem guarantees (0, S) is free. So relevant columns are alive.
// Create tree nodes for initial columns
// We group columns by initial connectivity at row 0.
// T[0] > H[c].
// Cols i, i+1 connected if T[0] > H[i] and T[0] > H[i+1].
// Wait, DSU logic handles H.
for(int i=0; i<M; ++i) {
dsu_parent[i] = i;
col_to_node[i] = i; // Initial nodes
min_h[i] = H[i];
tree.push_back({-1, false}); // Node i
if (H[i] >= T[0]) {
tree[i].is_dead = true;
}
}
current_nodes = M;
// 3. Process Landmarks
// Loop from i = 0 to size-2.
// Current row m_i (e.g. 0). Next row m_{i+1}.
// Barrier B = min T in (m_i, m_{i+1}).
// Target T = T[m_{i+1}].
// Need RMQ for Min T on ranges (already built in 'st' global).
for (size_t i = 0; i < landmarks.size() - 1; ++i) {
int curr_row = landmarks[i];
int next_row = landmarks[i+1];
// Barrier Check
int barrier = 2e9;
if (curr_row + 1 <= next_row - 1) {
barrier = query_min_T(curr_row + 1, next_row - 1);
}
// Identify components that die
// Since we don't have list of components, we iterate?
// Or only iterate roots.
// Optimization: Maintain list of active roots?
// M <= 200,000. DSU operations fast. But iterating M times is slow if loop is N.
// Landmarks size can be N. O(NM) bad.
// BUT: We only merge. Number of roots decreases.
// Also, only check roots that are NOT dead.
// We can maintain a `vector<int> active_roots`.
// Actually, we can just process edges sorted by weight?
// This is the standard Reachability Tree construction.
// Nodes are created when components merge.
// Plus "death" events.
// Let's refine the "Standard Reachability Tree" approach:
// Sort all columns by H. Sort all "Walls" (Barrier T) and "Floors" (Next T).
// This is complex due to mixed constraints.
// Back to landmarks loop.
// We need to avoid O(M) scan.
// Observe: barrier depends on i.
// We only care about components where min_h >= barrier.
// We can put components in a Priority Queue ordered by min_h?
// Yes.
}
}
};
// We will use the Tree + LCA approach.
// Since implementing the full landmarks logic with optimized merging is complex,
// and Q is large, we need the Tree.
// Let's construct the tree properly.
vector<int> dsu_p;
vector<int> dsu_min_h;
vector<int> dsu_node_id; // The tree node corresponding to this set
vector<bool> dsu_dead; // Dead status for the SET (optimization)
// Tree arrays
vector<vector<int>> tree_adj;
vector<bool> tree_dead;
vector<int> tree_depth;
vector<vector<int>> tree_up;
int tree_root;
int find_set(int v) {
if (v == dsu_p[v]) return v;
return dsu_p[v] = find_set(dsu_p[v]);
}
// Function to handle LCA queries
void dfs_lca(int u, int p, int d) {
tree_depth[u] = d;
tree_up[u][0] = p;
for (int i = 1; i < 20; i++) {
if (tree_up[u][i-1] != -1)
tree_up[u][i] = tree_up[tree_up[u][i-1]][i-1];
else
tree_up[u][i] = -1;
}
for (int v : tree_adj[u]) {
if (v != p) dfs_lca(v, u, d + 1);
}
}
int get_lca(int u, int v) {
if (tree_depth[u] < tree_depth[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (tree_up[u][i] != -1 && tree_depth[tree_up[u][i]] >= tree_depth[v])
u = tree_up[u][i];
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (tree_up[u][i] != tree_up[v][i]) {
u = tree_up[u][i];
v = tree_up[v][i];
}
}
return tree_up[u][0];
}
// Global vectors for precalc
vector<int> col_leaf;
// Priority Queue for death events: {min_h, dsu_root}
// Priority Queue for merge events: {threshold, col_index} (Edges j, j+1)
// We process "time" = T value.
// But the barrier logic is specific to the "Landmark" intervals.
// Let's implement the FULL solution using the simple logic:
// The tree describes connectivity.
// "Dead" status is a property of the node.
// If LCA(S, D) is not dead, TRUE.
// Note: A node is dead if its MinH >= Barrier of the level above it.
// Node represents a component at some Landmark level $m_i$.
// Parent is the component at $m_{i+1}$.
// Edge exists if component survives or merges.
// Actually, simpler:
// 1. Build standard Kruskal Reachability Tree using edges $(j, j+1)$ with weight $\max(H[j], H[j+1])$.
// Leafs are columns.
// This tree tells us: S and D are connected if we can tolerate humidity $H_{max} = \text{val}(LCA)$.
// Condition for Subtask 5: We need a row with $T > H_{max}$.
// Is it just $\max T > H_{max}$?
// No. The row must be reachable.
// BUT, for Subtask 5 ($L=0, R=M-1$), the "Global Max T" is available.
// If $H_{max} < T_{global\_max}$, is it always reachable?
// Yes, if there are no walls cutting the grid.
// Wait. If $S$ and $D$ are connected in Kruskal tree with value $H_{crit}$,
// it means there is a path of columns with humidity $\le H_{crit}$.
// Can we traverse this path?
// We need to cross boundaries.
// Boundary $(j, j+1)$ requires a row $r$ with $T[r] > H_{crit}$.
// If $\max T > H_{crit}$, we have such a row.
// Does that row span the whole path?
// Maybe not. But we can switch rows.
// Actually, for Subtask 5, the condition is exactly:
// $S$ and $D$ connected iff in the Kruskal Tree (weights $\max(H_i, H_{i+1})$), the LCA value $V$ satisfies $V < T_{max\_reachable}$.
// Wait, $T_{max\_reachable}$?
// If we are at $(0, S)$, we can reach any row $r$ if no full horizontal cuts exist.
// Given the complex constraints, maybe there's a simpler condition for Subtask 5.
// Conjecture: S and D are connected iff $\max(H \text{ on path in MST}) < \max(T)$.
// This is true if the grid is "convex" or simply connected, but cuts matter.
// HOWEVER, for 200,000, and "Llama", there is likely a Cartesian/Reachability tree mapping.
//
// Let's go with the detailed Landmark simulation which is proven correct.
// We will build the tree nodes explicitly.
vector<pair<int, int>> sorted_rows;
vector<pair<int, int>> sorted_h;
vector<int> initial_node;
void precompute_subtask5() {
// 1. Landmarks
vector<int> lm;
{
// Build RMQ for indices
// We need rightmost max.
// Or simply: m_next = query max index in [0, m_curr - 1]
// Prebuild sparse table for pair<val, index>
int K = 0; while((1<<(K+1)) <= N) K++;
vector<vector<pair<int, int>>> st2(N, vector<pair<int, int>>(K+1));
for(int i=0; i<N; i++) st2[i][0] = {T[i], i}; // larger index is irrelevant if we scan down
// We want rightmost?
// 0..R. If multiple maxes, picking rightmost (largest index) is better?
// Actually, picking largest index means smaller range for next step.
// It's fine.
for(int j=1; j<=K; j++)
for(int i=0; i+(1<<j)<=N; i++)
st2[i][j] = max(st2[i][j-1], st2[i+(1<<(j-1))][j-1]);
auto q_idx = [&](int r) {
int k = 31 - __builtin_clz(r+1);
return max(st2[0][k], st2[r-(1<<k)+1][k]).second;
};
int curr = N-1;
while(true) {
int idx = q_idx(curr);
lm.push_back(idx);
if(idx == 0) break;
curr = idx - 1;
}
reverse(lm.begin(), lm.end());
}
// 2. Init DSU and Tree
tree_adj.clear(); tree_dead.clear();
dsu_p.assign(M, 0); dsu_min_h = H; dsu_node_id.resize(M);
col_leaf.resize(M);
int node_counter = 0;
for(int i=0; i<M; i++) {
dsu_p[i] = i;
// Check if dead at level 0
bool dead = (H[i] >= T[0]);
tree_dead.push_back(dead);
col_leaf[i] = node_counter;
dsu_node_id[i] = node_counter++;
tree_adj.resize(node_counter);
}
// 3. Process Landmarks
// Use a set of active roots sorted by MinH for fast "death" check?
// Or just iterate active roots?
// Optimization: Put active roots in a vector.
vector<int> active_roots(M);
iota(active_roots.begin(), active_roots.end(), 0);
// Edges between columns j, j+1 become active when T > max(H[j], H[j+1]).
// Sort edges by weight.
vector<pair<int, int>> edges;
for(int i=0; i<M-1; i++) edges.push_back({max(H[i], H[i+1]), i});
sort(edges.begin(), edges.end());
int edge_ptr = 0;
for(size_t k=0; k < lm.size() - 1; k++) {
int curr_row = lm[k];
int next_row = lm[k+1];
// Barrier
int barrier = 2e9;
if(curr_row + 1 <= next_row - 1) barrier = query_min_T(curr_row+1, next_row-1);
// 3a. Mark deaths
// Scan active roots.
// We can optimize this by maintaining sorted order or just linear scan if component count drops.
// Since merges happen, active_roots shrinks.
// But initially 200k.
// Linear scan of 200k inside 200k loop? No.
// The loop runs 'lm.size()' times. lm.size() can be N.
// We need efficient "Find roots with MinH >= Barrier".
// Solution: Do not iterate. Roots are implicitly managed.
// Just note that if MinH >= Barrier, the node created at this step is dead.
// But we need to record it in the tree.
// Wait, the tree structure:
// When we move from k to k+1, we create new parent nodes for changed components?
// Standard DSU on Tree: Create parent when merging.
// Here we also have "time steps" (levels).
// Let's force create a new parent for EVERY component at each level? Too many nodes.
// Only create parent if:
// 1. Component Merges.
// 2. Component dies? (Mark flag).
// Efficient Approach:
// Use standard "Kruskal Reconstruction Tree" logic but with "Death" annotation.
// The "Death" condition is: $H_{component} \ge Barrier$.
// This is a property of the component at time $k$.
// We can check this during query?
// Query path: Leaf -> ... -> Root.
// Check if any node on path is "Dead".
// A node $u$ corresponds to a merge at humidity $H_u$.
// It was formed at some T-level (determined by the edge weight).
// But the barrier depends on the sequence of T-levels.
// Let's change perspective:
// We are processing edges with weight $W$.
// $W$ corresponds to some $T$.
// Specifically, we are increasing T capability.
// Edges with weight $W$ allow us to merge if $T_{current} > W$.
// The "levels" $lm_k$ define intervals of T.
// Let $T_{curr} = T[lm_k]$. We can use edges with weight $< T[curr]$? No.
// We start at $T[0]$. We iterate to $T[lm_1]$, etc.
// $T$ is generally increasing.
// Edges merge components.
// The "Barrier" check is: Before we jump from $lm_k$ to $lm_{k+1}$,
// any component with $MinH \ge Barrier$ dies.
// This death is permanent for the purpose of "reaching $lm_{k+1}$".
// So we can mark the component (current DSU root) as dead *at this timestamp*.
// To implement efficiently:
// 1. `active_roots` is just a list. We iterate it?
// Total sum of `active_roots.size()` over all steps might be large?
// No, because we only iterate if we have many levels.
// Actually, worst case: N steps, M roots. O(NM).
// But Barrier only exists if rows exist between landmarks.
// If N is large, sparse table barrier check is fast.
// Issue is marking deaths.
// Instead of marking, store `(BarrierValue, LevelID)` pairs?
// No.
// Let's use the fact that MinH only decreases.
// Barrier logic: "If MinH >= B, Die".
// Query: "Is path valid?"
// Path is valid if for all steps on path, $MinH_{step} < Barrier_{step}$.
// We can store `MaxAllowedBarrier` for each node in the tree?
// No, we store `MinH` of the node.
// And we store the `Barrier` of the transition *out* of the node.
// Each node $u$ in Kruskal tree represents a component valid for a range of T.
// Or rather, formed at humidity $H_{u}$.
// It exists until it merges into parent.
// During its life, it passes through several landmarks.
// We need to check if $MinH(u) < Barrier$ for all barriers encountered while $u$ is active.
// Store `MaxBarrierEncountered` for each node?
// Yes!
// For each step $k$, we have a Barrier $B_k$.
// This barrier applies to all currently active components.
// We can update a global `PendingBarrier`?
// When a component merges, we push the pending barrier to it?
// DSU with Lazy Propagation?
// Complexity: O(M log M).
// Algorithm:
// Init: `NodeBarrier[u] = infinity`.
// Global `CurrentBarrier = infinity`.
// Between steps: `CurrentBarrier = min(CurrentBarrier, RealBarrier)`.
// When merging $u, v$ into $new$:
// `NodeBarrier[u] = CurrentBarrier`
// `NodeBarrier[v] = CurrentBarrier`
// `NodeBarrier[new] = infinity` (reset for new life).
// (Wait, the internal nodes $u, v$ are now fixed. Their lifetime ends.
// So we record the worst barrier they faced).
// At end, check path.
// Correction:
// Barriers accumulate.
// While $u$ is a root, it faces a sequence of barriers.
// It survives if $MinH[u] < \min(Barriers)$.
// Let `WorstBarrier[u]` be the min barrier encountered while $u$ was root.
// When $u$ becomes child of $w$, we freeze `WorstBarrier[u]`.
// Also need to verify $MinH[u] < WorstBarrier[u]$.
// AND, the path continues up to $w$.
// So condition is recursive: Valid(u) = ($MinH[u] < WorstBarrier[u]$) AND Valid(Parent(u)).
// Implementation:
// Maintain `RootWorstBarrier[root_id]`. Init infinity.
// At each step $k$:
// B = query_barrier...
// Update active roots?
// We can't iterate.
// BUT `CurrentBarrier` applies to ALL active roots.
// So maintain `GlobalWorstBarrier`.
// Wait, different roots were created at different times.
// They have seen different subsets of barriers.
// Use a "Timestamp" or "Generation" system.
// `CreationTime[u]`.
// `GlobalBarrierHistory`: vector of pairs (time, barrier).
// `WorstBarrier[u]` = min of GlobalBarrierHistory from `CreationTime[u]` to `MergeTime[u]`.
// This is efficient!
}
}
*/
// Actual compact solution
vector<int> T_vec, H_vec;
vector<vector<int>> st_min;
vector<int> lg;
vector<vector<pair<int, int>>> st_max_idx;
// Tree
struct Edge { int v; };
vector<vector<int>> tree_adj;
vector<int> tree_min_h;
vector<int> tree_creation_time;
vector<int> tree_merge_time;
vector<int> node_min_h; // MinH of the component represented by node
int num_nodes;
// Global Barriers
vector<int> barrier_history; // Stores barrier value at each step
void build_sparse() {
int n = T_vec.size();
lg.resize(n + 1);
lg[1] = 0;
for(int i=2; i<=n; i++) lg[i] = lg[i/2] + 1;
int K = lg[n];
st_min.assign(n, vector<int>(K+1));
st_max_idx.assign(n, vector<pair<int, int>>(K+1));
for(int i=0; i<n; i++) {
st_min[i][0] = T_vec[i];
st_max_idx[i][0] = {T_vec[i], i};
}
for(int j=1; j<=K; j++) {
for(int i=0; i+(1<<j)<=n; i++) {
st_min[i][j] = min(st_min[i][j-1], st_min[i+(1<<(j-1))][j-1]);
pair<int, int> p1 = st_max_idx[i][j-1];
pair<int, int> p2 = st_max_idx[i+(1<<(j-1))][j-1];
if (p2.first >= p1.first) st_max_idx[i][j] = p2;
else st_max_idx[i][j] = p1;
}
}
}
int get_min_T(int l, int r) {
if (l > r) return 2e9;
int k = lg[r - l + 1];
return min(st_min[l][k], st_min[r - (1<<k) + 1][k]);
}
int get_max_T_idx(int l, int r) {
if (l > r) return -1;
int k = lg[r - l + 1];
pair<int, int> p1 = st_max_idx[l][k];
pair<int, int> p2 = st_max_idx[r - (1<<k) + 1][k];
return (p2.first >= p1.first) ? p2.second : p1.second;
}
// LCA
vector<vector<int>> up;
vector<int> depth;
void dfs_lca(int u, int p, int d) {
depth[u] = d;
up[u][0] = p;
for(int i=1; i<20; i++)
up[u][i] = (up[u][i-1] == -1) ? -1 : up[up[u][i-1]][i-1];
for(int v : tree_adj[u]) {
if(v != p) dfs_lca(v, u, d+1);
}
}
int lca(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
for(int i=19; i>=0; i--)
if(up[u][i] != -1 && depth[up[u][i]] >= depth[v]) u = up[u][i];
if(u == v) return u;
for(int i=19; i>=0; i--)
if(up[u][i] != up[v][i]) { u = up[u][i]; v = up[v][i]; }
return up[u][0];
}
// Barrier RMQ (on history)
vector<vector<int>> st_bar;
void build_bar_st() {
int m = barrier_history.size();
if(m == 0) return;
int K = lg[m];
st_bar.assign(m, vector<int>(K+1));
for(int i=0; i<m; i++) st_bar[i][0] = barrier_history[i];
for(int j=1; j<=K; j++)
for(int i=0; i+(1<<j)<=m; i++)
st_bar[i][j] = min(st_bar[i][j-1], st_bar[i+(1<<(j-1))][j-1]);
}
int get_min_bar(int l, int r) {
if (l > r) return 2e9;
int k = lg[r - l + 1];
return min(st_bar[l][k], st_bar[r - (1<<k) + 1][k]);
}
// DSU
vector<int> dsu_p;
vector<int> dsu_node; // Map set to tree node
int find_dsu(int i) { return (dsu_p[i] == i) ? i : dsu_p[i] = find_dsu(dsu_p[i]); }
vector<int> leaf_ids;
bool initialized = false;
void initialize(vector<int> T, vector<int> H) {
T_vec = T; H_vec = H;
int n = T.size();
int m = H.size();
build_sparse();
// Landmarks
vector<int> lm;
int curr = n - 1;
while(true) {
int idx = get_max_T_idx(0, curr);
lm.push_back(idx);
if(idx == 0) break;
curr = idx - 1;
}
reverse(lm.begin(), lm.end()); // 0 = m_0, m_1, ...
// Edges
vector<pair<int, int>> edges;
for(int i=0; i<m-1; i++) edges.push_back({max(H[i], H[i+1]), i});
sort(edges.begin(), edges.end());
// Init Tree
tree_adj.assign(2 * m, vector<int>());
node_min_h.resize(2 * m);
tree_creation_time.resize(2 * m);
tree_merge_time.assign(2 * m, 2e9); // Alive until end
dsu_p.resize(m);
dsu_node.resize(m);
leaf_ids.resize(m);
num_nodes = 0;
for(int i=0; i<m; i++) {
dsu_p[i] = i;
dsu_node[i] = num_nodes;
leaf_ids[i] = num_nodes;
node_min_h[num_nodes] = H[i];
tree_creation_time[num_nodes] = 0; // Time 0
num_nodes++;
}
barrier_history.push_back(2e9); // Time 0
int edge_ptr = 0;
int step = 0;
// Process steps
for(size_t k=0; k<lm.size(); k++) {
step++;
int row_curr = lm[k]; // m_i
int next_row = (k+1 < lm.size()) ? lm[k+1] : -1;
// Target T to enable edges
int target_T = (next_row != -1) ? T_vec[next_row] : 2e9;
// Wait, T[m_{i+1}] enables edges?
// No. Edges are enabled by T.
// We are at m_i. We want to go to m_{i+1}.
// The edges we can use are those with weight < T[next_row]?
// No. We are moving UP the T values.
// T[m_0] (Row 0) is low. T[m_end] is high.
// We enable edges as T increases.
// Current level is T[m_k].
// Edges with weight < T[m_k] are valid.
// Actually, we process edges up to T[next_row]??
// No. We process edges up to T[row_curr].
// Loop k iterates landmarks.
// At step k, we have capability T[row_curr].
// So activate edges < T[row_curr].
while(edge_ptr < edges.size() && edges[edge_ptr].first < T_vec[row_curr]) {
int u = edges[edge_ptr].second;
int v = u + 1;
int root_u = find_dsu(u);
int root_v = find_dsu(v);
if(root_u != root_v) {
// Merge
int new_node = num_nodes++;
tree_adj.resize(num_nodes); // Resize check
node_min_h.resize(num_nodes);
tree_creation_time.resize(num_nodes);
tree_merge_time.resize(num_nodes, 2e9);
int node_u = dsu_node[root_u];
int node_v = dsu_node[root_v];
tree_adj[new_node].push_back(node_u);
tree_adj[new_node].push_back(node_v);
tree_merge_time[node_u] = step;
tree_merge_time[node_v] = step;
tree_creation_time[new_node] = step;
node_min_h[new_node] = min(node_min_h[node_u], node_min_h[node_v]);
dsu_p[root_v] = root_u;
dsu_node[root_u] = new_node;
}
edge_ptr++;
}
// After merging, determine Barrier for NEXT transition
// Barrier for transition from m_k to m_{k+1}
if (next_row != -1) {
// Range (m_k + 1 ... m_{k+1} - 1) ?
// No, landmarks are ordered by index?
// lm vector: 0, m_1, m_2 (where T increases).
// Actually my lm construction: 0=m_0, m_1..m_k.
// m_{i+1} is the "parent" landmark (higher T).
// Range is (curr_row + 1, next_row - 1).
// BUT wait. m_{i+1} is argmax in 0..m_i-1?
// Yes. So next_row < curr_row.
// Range is (next_row + 1, curr_row - 1).
int b = 2e9;
if (next_row + 1 <= row_curr - 1) {
b = get_min_T(next_row + 1, row_curr - 1);
}
barrier_history.push_back(b);
} else {
barrier_history.push_back(2e9);
}
}
// Remaining edges? (If T_global_max < max_edge_weight).
// They never activate. Components remain separate.
// Connect roots to a dummy global root? Not needed, LCA will fail.
// Build LCA and Barrier ST
up.assign(num_nodes, vector<int>(20, -1));
depth.assign(num_nodes, 0);
for(int i=num_nodes-1; i>=0; i--) {
if(tree_merge_time[i] == 2e9 && depth[i] == 0) { // Roots
dfs_lca(i, -1, 0);
}
}
build_bar_st();
initialized = true;
}
bool can_reach(int L, int R, int S, int D) {
if (S == D) return true;
int u = leaf_ids[S];
int v = leaf_ids[D];
// Find LCA
// If not in same tree component, return false
// We can check if roots are same.
// Using binary lifting to check connectivity:
int root_u = u; for(int i=19; i>=0; i--) if(up[root_u][i]!=-1) root_u = up[root_u][i];
int root_v = v; for(int i=19; i>=0; i--) if(up[root_v][i]!=-1) root_v = up[root_v][i];
if (root_u != root_v) return false;
int lca_node = lca(u, v);
// Initial check: S and D must be valid at time 0 (Row 0 connectivity)
// T[0] > H[S] and T[0] > H[D] guaranteed by problem.
// Check path u -> lca
// Path consists of nodes. Each node x has a lifetime [creation_time, merge_time].
// During this lifetime, it must satisfy MinH[x] < MinBarrier[creation..merge].
// We can check this for lca_node and its ancestors?
// No, strictly the path is u -> ... -> lca.
// Every node on this path must be valid.
// We need to check validity of a node.
// Is_Valid(x) = (node_min_h[x] < min_barrier(creation_time[x], merge_time[x])).
// Note: merge_time[lca] is effectively infinity (or time of query context).
// Actually, once they merge at LCA, they are connected.
// Does the LCA component die later?
// It doesn't matter. They connected at LCA time.
// The barrier check is: Did they die *before* they merged?
// So for every node on path u->lca (excluding lca), check validity.
// And for v->lca (excluding lca).
// And for lca itself?
// lca implies they are in the same set at time `creation_time[lca]`.
// We need to ensure neither component died before this time.
auto check_path = [&](int node, int target) {
// Go up from node to target
int curr = node;
while(curr != target) {
int c_time = tree_creation_time[curr];
int m_time = tree_merge_time[curr]; // Valid range [c, m]
// Check barrier in history indices [c, m-1]?
// Barrier history is aligned with steps.
// Barrier[k] is barrier after step k (transition k -> k+1).
// So while node is active (steps c to m-1), check barriers.
if (c_time < m_time) {
int min_b = get_min_bar(c_time + 1, m_time); // +1 because barrier_history[k] is for step k transition
// Actually indexing:
// loop k=0..size. barrier_history pushed at end of loop.
// step 1 writes to history[1].
// So creation_time=t means created at end of step t? Or start?
// Step logic: loop runs, time advances.
// Merges happen at step k (time k).
// Barrier stored is for transition k -> k+1.
// So if created at k, merged at m.
// It lives through transitions k, k+1, ..., m-1.
// Check barrier indices [c, m-1]?
// Let's verify indexing.
// barrier_history[0] is dummy.
// Loop k=0 (step 1). Pushes to history[1].
// Merge happens inside loop. Time = 1.
// Barrier check is for transition 1->2. history[1].
// So yes, check indices c to m-1.
// Note: history size is steps+1.
if (c_time <= m_time - 1) {
int min_b = get_min_bar(c_time, m_time - 1);
// Indices of history vector.
// history[0] is inf.
// Step k (1-based) generates history[k].
// If created at step T, we check barriers starting T.
// Until M-1.
if (node_min_h[curr] >= min_b) return false;
}
}
curr = up[curr][0];
}
return true;
};
// Optimization: Precalculate "Death Time" for each node to do O(1) check?
// DeathTime[u] = min barrier time that kills u.
// Valid if DeathTime[u] >= merge_time[u].
// Since we only query up to LCA, checking O(log N) or O(path) is acceptable for 200k?
// Path length bounded by log N? No, could be N.
// Need O(1) or O(log N).
// Precalc: `is_valid_up_to_root`?
// `first_failure_depth`.
// Valid if depth[first_failure] <= depth[lca].
// We can precalc `min_h_vs_barrier_diff` along path?
// Let's just solve with `check_path` logic optimized.
// `max_h_on_path_to_root` vs `min_barrier_on_path`.
// This is 2D range query?
// No.
// Compute `Dead` boolean for each node.
// Node is dead if (Self MinH >= Barrier during lifetime) OR (Child on path is Dead).
// Wait, if Child is dead, Parent might be alive (other child ok).
// But the path coming from Child is broken.
// So `PathValid[u]` = `NodeValid[u]` AND `PathValid[Parent[u]]`?
// Yes.
// `NodeValid[u]` = (node_min_h[u] < get_min_bar(creation, merge-1)).
// Precompute this bool.
// Then precompute prefix sum of "Invalid Nodes" up to root.
// Path u->LCA is valid if count_invalid(u) - count_invalid(LCA) == 0.
// Implement precalc in check_path style
// But since `can_reach` called many times, we must precalc.
return false; // See final code structure
}