#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int N, M;
vector<int> T, H;
void initialize(std::vector<int> t, std::vector<int> h) {
N = t.size();
M = h.size();
T = t;
H = h;
}
bool can_reach(int L, int R, int S, int D) {
// If start and destination are the same
if (S == D) return true;
// Special case for N = 1
if (N == 1) {
// Just check connectivity in row 0
int minCol = min(S, D);
int maxCol = max(S, D);
for (int j = minCol; j <= maxCol; j++) {
if (T[0] <= H[j]) return false;
}
return true;
}
int width = R - L + 1;
// Dynamic allocation for visited array
vector<bool> visited(N * width, false);
queue<int> q;
// Helper function to convert (row, col) to index
auto getIndex = [width, L](int row, int col) {
return row * width + (col - L);
};
// Start from (0,S)
int start_idx = getIndex(0, S);
q.push(start_idx);
visited[start_idx] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
int row = curr / width;
int col = (curr % width) + L;
// Check if we reached the destination
if (row == 0 && col == D) {
return true;
}
// Try all 4 directions
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};
for (int dir = 0; dir < 4; dir++) {
int new_row = row + dr[dir];
int new_col = col + dc[dir];
// Check bounds
if (new_row < 0 || new_row >= N) continue;
if (new_col < L || new_col > R) continue;
// Check if cell is free of vegetation
if (T[new_row] <= H[new_col]) continue;
int new_idx = getIndex(new_row, new_col);
// Check if already visited
if (visited[new_idx]) continue;
// Mark as visited and add to queue
visited[new_idx] = true;
q.push(new_idx);
}
}
return false;
}
