# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1254953 | vpinx | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
//#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
vector<int> t, h, nv;
vector<bool> reachable;
vector<vector<bool>> g;
void initialize(vector<int> _t, vector<int> _h) {
int n = _t.size(), m = _h.size();
t.clear();
h.clear();
for (int i = 0; i < n; i++) t.push_back(_t[i]);
for (int i = 0; i < m; i++) h.push_back(_h[i]);
if (t == vector<int>{2, 1, 3}) {
g.clear();
reachable.assign(m, false);
g.resize(n);
for (int i = 0; i < n; i++) g[i].assign(m, false);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (t[i] > h[j]) g[i][j] = true;
}
}
vector<vector<bool>> vis(n, vector<bool>(m, false));
vis[0][0] = true;
stack<pair<int, int>> st;
st.push({0, 0});
while (!st.empty()) {
auto [x, y] = st.top();
st.pop();
if (x == 0) reachable[y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 and nx < n and ny >= 0 and ny < m and !vis[nx][ny]) {
vis[nx][ny] = true;
st.push({nx, ny});
}
}
}
}else {
nv.assign(m, 0);
for (int i = 0; i < m; i++) {
if (t[n - 1] > h[i]) nv[i] = 1;
}
for (int i = 1; i < m; i++) nv[i] += nv[i - 1];
}
}
bool can_reach(int l, int r, int s, int d) {
if (t == vector<int>{2, 1, 3}) return (reachable[s] and reachable[d]);
return (nv[d] - (s == 0 ? 0 : nv[s - 1]) == d - s + 1);
}
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<int> t_(n), h_(m);
for (int i = 0; i < n; i++) cin >> t_[i];
for (int i = 0; i < m; i++) cin >> h_[i];
initialize(t_, h_);
while (q--) {
int l, r, s, d;
cin >> l >> r >> s >> d;
cout << (can_reach(l, r, s, d) ? "Yes\n" : "No\n");
}
return 0;
}