//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
vector<int> xv;
pii orig[maxn];
pii pos[maxn];
vector<int> pnt[maxn], ind[maxn];
bool con[maxn];
int to[18][maxn];
int main() {
io
int r, c, n;
cin >> r >> c >> n;
for (int i = 0;i < n;i++) {
cin >> orig[i].ff >> orig[i].ss;
xv.push_back(orig[i].ff);
}
sort(xv.begin(), xv.end());
xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
for (int i = 0;i < n;i++) {
int posid = lower_bound(xv.begin(), xv.end(), orig[i].ff) - xv.begin();
pnt[posid].push_back(orig[i].ss);
}
int tot = 1;
for (int i = 0;i < n;i++) {
sort(pnt[i].begin(), pnt[i].end());
for (int j = 0;j < pnt[i].size();j++) {
pos[tot] = make_pair(i, pnt[i][j]);
ind[i].push_back(tot++);
}
if (i < n - 1) {
con[i] = xv[i + 1] == xv[i] + 1 ? 1 : 0;
}
}
pos[tot] = make_pair(r + 1, c + 1);
for (int i = 1;i <= tot;i++) {
if (con[pos[i].ff]) {
int id = lower_bound(pnt[pos[i].ff + 1].begin(), pnt[pos[i].ff + 1].end(), pos[i].ss) - pnt[pos[i].ff + 1].begin();
if (id >= ind[pos[i].ff + 1].size()) {
to[0][i] = tot;
} else {
to[0][i] = ind[pos[i].ff + 1][id];
}
} else {
to[0][i] = tot;
}
}
for (int i = 1;i < 18;i++) {
for (int j = 1;j <= tot;j++) to[i][j] = to[i - 1][to[i - 1][j]];
}
int t;
cin >> t;
while (t--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2) {
cout << (y1 <= y2 ? "Yes" : "No") << "\n";
} else {
int comp = lower_bound(xv.begin(), xv.end(), x1) - xv.begin();
int ans = 1;
if (comp >= xv.size() || xv[comp] != x1) {
ans = 0;
} else {
x2--;
int dif = x2 - x1;
int id = lower_bound(pnt[comp].begin(), pnt[comp].end(), y1) - pnt[comp].begin();
if (id >= pnt[comp].size()) {
ans = 0;
} else {
int cur = ind[comp][id], cnt = 0;
while (dif) {
if (dif & 1) cur = to[cnt][cur];
cnt++, dif>>=1;
}
if (pos[cur].ss > y2) {
ans = 0;
}
}
}
cout << (ans ? "Yes" : "No") << "\n";
}
}
}
/*
4 5 2
2 2
3 4
3
2 1 4 5
1 2 1 4
2 3 4 4
*/
Compilation message
trampoline.cpp: In function 'int main()':
trampoline.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0;j < pnt[i].size();j++) {
| ~~^~~~~~~~~~~~~~~
trampoline.cpp:54:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if (id >= ind[pos[i].ff + 1].size()) {
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:77:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | if (comp >= xv.size() || xv[comp] != x1) {
| ~~~~~^~~~~~~~~~~~
trampoline.cpp:83:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if (id >= pnt[comp].size()) {
| ~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
21612 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
30476 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
109 ms |
30504 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
117 ms |
30016 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Runtime error |
166 ms |
61732 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
33680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
19916 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
39812 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
