#include "bits/stdc++.h"
using namespace std;
#include "debug.h"
class dsu {
public:
vector<int> p;
int n;
dsu(int n) : n(n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
void clear() {
iota(p.begin(), p.end(), 0);
}
int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
int unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return y;
}
assert(false);
return -1;
}
};
void solve() {
int r, c, n;
cin >> r >> c >> n;
vector<pair<int, int>> a(n);
vector<int> events;
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
events.push_back(a[i].first);
if (i + 1 < r) {
events.push_back(a[i].first + 1);
}
}
std::sort(events.begin(), events.end());
events.resize(std::unique(events.begin(), events.end()) - events.begin());
const int N = (int) events.size();
vector<vector<int>> points(N);
for (auto& [x, y] : a) {
x = std::lower_bound(events.begin(), events.end(), x) - events.begin();
points[x].push_back(y);
}
int q;
cin >> q;
vector<int> ans(q);
vector<vector<array<int, 3>>> ev(N);
for (int i = 0; i < q; i++) {
int x, y, x2, y2;
cin >> x >> y >> x2 >> y2;
if (x2 < x || y2 < y) {
continue;
}
if (x == x2) {
ans[i] = 1;
continue;
}
int ix = std::lower_bound(events.begin(), events.end(), x) - events.begin();
int ix2 = std::lower_bound(events.begin(), events.end(), x2) - events.begin();
if (ix == N || events[ix] != x || ix2 == N || events[ix2] != x2) {
continue;
}
x = ix, x2 = ix2;
ev[x].push_back({y, i, 0});
ev[x2].push_back({y2, i, 1});
}
dsu g(q);
vector<int> info(q);
set<pair<int, int>> mn;
for (int x = 0; x < N; x++) {
for (auto [y, i, t] : ev[x]) {
if (t == 1) {
int my = info[g.get(i)];
ans[i] = my <= y;
} else {
mn.insert({y, i});
info[i] = y;
}
}
std::sort(points[x].begin(), points[x].end());
set<pair<int, int>> mn2;
for (auto y : points[x]) {
int rt = -1;
while (!mn.empty() && mn.begin()->first <= y) {
if (rt == -1) {
rt = mn.begin()->second;
} else {
rt = g.unite(rt, mn.begin()->second);
}
mn.erase(mn.begin());
}
if (rt != -1) {
info[rt] = y;
mn2.insert({y, rt});
}
}
for (auto [_, rt] : mn) {
info[rt] = c + 1;
}
mn = mn2;
}
for (int i = 0; i < q; i++) {
cout << (ans[i] ? "Yes\n" : "No\n");
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
Compilation message
trampoline.cpp:5:10: fatal error: debug.h: No such file or directory
5 | #include "debug.h"
| ^~~~~~~~~
compilation terminated.
