//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <assert.h>
#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:xv) cout << i << endl;
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 < xv.size();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 < xv.size() - 1) {
con[i] = xv[i + 1] == xv[i] + 1 ? 1 : 0;
}
}
pos[tot] = make_pair(maxn - 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()) {
ans = 0;
} else if (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 >= ind[comp].size() || dif >= maxn) {
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
1 2
2 4
3
2 1 4 5
1 2 1 4
3 3 4 4
*/
Compilation message
trampoline.cpp: In function 'int main()':
trampoline.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0;i < xv.size();i++) {
| ~~^~~~~~~~~~~
trampoline.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int j = 0;j < pnt[i].size();j++) {
| ~~^~~~~~~~~~~~~~~
trampoline.cpp:50:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if (i < xv.size() - 1) {
| ~~^~~~~~~~~~~~~~~
trampoline.cpp:58:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (id >= ind[pos[i].ff + 1].size()) {
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (comp >= xv.size()) {
| ~~~~~^~~~~~~~~~~~
trampoline.cpp:89:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if (id >= ind[comp].size() || dif >= maxn) {
| ~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
21572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
30380 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
110 ms |
30360 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
95 ms |
29884 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Runtime error |
147 ms |
61412 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
30528 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
254 ms |
30264 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
262 ms |
30304 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
271 ms |
30660 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
273 ms |
30736 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
358 ms |
33100 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
20752 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
187 ms |
66568 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
