#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define fi first
#define se second
using namespace std;
map<int, vector<pair<int, int>>> M;
pair<int, int> pts[200001];
int nxt[200001], anc[200001][20];
int kth_anc(int u, int k){
for(int j = 19; j >= 0; j--){
if(k >= (1 << j)) u = anc[u][j], k -= (1 << j);
}
return u;
}
int main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
int r, c, n; cin >> r >> c >> n;
for(int i = 0; i < n; i++){
int x, y; cin >> x >> y;
M[x].push_back({y, i});
pts[i] = {x, y};
}
for(auto& i : M) sort(all(i.second));
for(int i = 0; i < n; i++){
int x = pts[i].fi, y = pts[i].se;
if(M.count(x + 1) && lower_bound(all(M[x + 1]), pair<int, int>{y, -1}) != M[x + 1].end()){
pair<int, int> p = *lower_bound(all(M[x + 1]), pair<int, int>{y, -1});
nxt[i] = p.se;
}else{
nxt[i] = i;
}
}
for(int j = 0; j < n; j++) anc[j][0] = nxt[j];
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
anc[j][i] = anc[anc[j][i - 1]][i - 1];
}
}
int q; cin >> q;
for(int i = 0; i < q; i++){
int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
if(r1 == r2 && c1 <= c2) { cout << "Yes" << endl; continue; }
if(c1 > c2 || r1 > r2) { cout << "No" << endl; continue; }
if(M.count(r1) && lower_bound(all(M[r1]), pair<int, int>{c1, -1}) != M[r1].end()){
int fr = lower_bound(all(M[r1]), pair<int, int>{c1, -1})->se;
int v = kth_anc(fr, r2 - r1 - 1);
if(pts[v].fi != r2 - 1 || pts[v].se > c2) { cout << "No" << endl; continue; }
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1236 KB |
200 token(s): yes count is 21, no count is 179 |
2 |
Correct |
8 ms |
1492 KB |
200 token(s): yes count is 70, no count is 130 |
3 |
Correct |
5 ms |
1108 KB |
197 token(s): yes count is 25, no count is 172 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
197 ms |
21356 KB |
4000 token(s): yes count is 99, no count is 3901 |
2 |
Correct |
203 ms |
23476 KB |
4000 token(s): yes count is 91, no count is 3909 |
3 |
Correct |
174 ms |
22140 KB |
4000 token(s): yes count is 4000, no count is 0 |
4 |
Correct |
212 ms |
23220 KB |
4000 token(s): yes count is 1991, no count is 2009 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
467 ms |
21100 KB |
200000 token(s): yes count is 110486, no count is 89514 |
2 |
Correct |
488 ms |
20984 KB |
200000 token(s): yes count is 114664, no count is 85336 |
3 |
Correct |
503 ms |
21196 KB |
200000 token(s): yes count is 86232, no count is 113768 |
4 |
Correct |
586 ms |
21952 KB |
200000 token(s): yes count is 94603, no count is 105397 |
5 |
Correct |
596 ms |
21796 KB |
200000 token(s): yes count is 94148, no count is 105852 |
6 |
Correct |
756 ms |
27556 KB |
200000 token(s): yes count is 97163, no count is 102837 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
852 KB |
5000 token(s): yes count is 3238, no count is 1762 |
2 |
Correct |
12 ms |
1108 KB |
5000 token(s): yes count is 3837, no count is 1163 |
3 |
Correct |
13 ms |
1620 KB |
5000 token(s): yes count is 4104, no count is 896 |
4 |
Correct |
12 ms |
1096 KB |
5000 token(s): yes count is 3934, no count is 1066 |
5 |
Correct |
14 ms |
1300 KB |
5000 token(s): yes count is 3384, no count is 1616 |
6 |
Correct |
11 ms |
1112 KB |
5000 token(s): yes count is 3390, no count is 1610 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
901 ms |
28792 KB |
200000 token(s): yes count is 171404, no count is 28596 |
2 |
Correct |
735 ms |
35460 KB |
200000 token(s): yes count is 161254, no count is 38746 |
3 |
Correct |
510 ms |
33108 KB |
200000 token(s): yes count is 117455, no count is 82545 |
4 |
Correct |
1088 ms |
52772 KB |
200000 token(s): yes count is 182118, no count is 17882 |
5 |
Correct |
692 ms |
39412 KB |
200000 token(s): yes count is 167565, no count is 32435 |
6 |
Correct |
522 ms |
32940 KB |
200000 token(s): yes count is 156797, no count is 43203 |
7 |
Correct |
520 ms |
32840 KB |
200000 token(s): yes count is 156797, no count is 43203 |
8 |
Correct |
490 ms |
32700 KB |
200000 token(s): yes count is 122100, no count is 77900 |
9 |
Correct |
857 ms |
39168 KB |
200000 token(s): yes count is 139670, no count is 60330 |
10 |
Correct |
901 ms |
39752 KB |
200000 token(s): yes count is 165806, no count is 34194 |
11 |
Correct |
1030 ms |
45260 KB |
200000 token(s): yes count is 175646, no count is 24354 |
12 |
Correct |
464 ms |
32556 KB |
200000 token(s): yes count is 134695, no count is 65305 |
13 |
Correct |
466 ms |
32908 KB |
200000 token(s): yes count is 126733, no count is 73267 |
14 |
Correct |
606 ms |
33540 KB |
200000 token(s): yes count is 155290, no count is 44710 |
15 |
Correct |
482 ms |
32668 KB |
200000 token(s): yes count is 129674, no count is 70326 |