This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int LOG = 19;
constexpr int INF = 1e9 + 9;
int x[N], y[N], jump[N][LOG], ans[N];
map<int, vector<pair<int, int>>> pos;
int get_nxt(int x, int y) {
auto it = lower_bound(all(pos[x]), make_pair(y, -INF));
return (it == pos[x].end() ? 0 : (*it).second);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int h, w, n;
cin >> h >> w >> n;
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i];
pos[x[i]].push_back({y[i], i});
}
for (auto &&[x, v] : pos)
sort(v.begin(), v.end());
for (int i = 1; i <= n; ++i)
jump[i][0] = get_nxt(x[i] + 1, y[i]);
for (int i = 0; i < n; ++i)
for (int j = 1; j < LOG; ++j)
jump[i][j] = jump[jump[i][j - 1]][j - 1];
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2) {
cout << (y1 <= y2 ? "Yes\n" : "No\n");
continue;
}
int v = get_nxt(x1, y1);
if (v == 0 || x[v] > x2 || y[v] > y2) {
cout << "No\n";
continue;
}
for (int j = LOG - 1; j >= 0; --j)
if (jump[v][j] != 0 && y[jump[v][j]] <= y2)
v = jump[v][j];
cout << (v == 0 || y[v] > y2 || x[v] < x2 - 1 ? "No\n" : "Yes\n");
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |