/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define taskname "bai3"
#define all(x) x.begin(), x.end()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
using namespace std;
const int mxN = 2e5 + 5;
const int base = 1e9 + 1;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int r, c, t, q, lg[mxN], pw[25];
int sparse_table[25][mxN];
vector<pii> v;
map<int, vector<pii>> mp;
bool sortbysec(const pii &a, const pii &b) {
if(a.ss != b.ss) return (a.ss < b.ss);
return (a.ff < b.ff);
}
void solve() {
cin >> r >> c >> t;
lg[1] = 0; pw[0] = 1;
for(int i = 2; i < mxN; ++i) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i < 20; ++i) pw[i] = pw[i - 1] * 2;
for(int i = 1; i <= t; ++i) {
int u, v1; cin >> u >> v1;
v.pb({u, v1});
}
sort(all(v));
for(int i = 0; i < t; ++i)
mp[v[i].ff].pb({v[i].ss, i});
sparse_table[0][t] = t;
for(int i = 0; i < t; ++i) {
if(mp.find(v[i].ff + 1) == mp.end()) {
sparse_table[0][i] = t;
continue;
}
auto it = lower_bound(all(mp[v[i].ff + 1]), make_pair(v[i].ss, 0));
if(it == mp[v[i].ff + 1].end()) sparse_table[0][i] = t;
else sparse_table[0][i] = (*it).ss;
}
for(int i = 1; i < 20; ++i) {
sparse_table[i][t] = t;
for(int j = 0; j < t; ++j) {
sparse_table[i][j] = sparse_table[i - 1][sparse_table[i - 1][j]];
}
}
cin >> q;
while(q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if(x1 > x2) {
cout << "No\n";
continue;
}
if(x1 == x2) {
if(y1 <= y2) {
cout << "Yes\n";
}
else cout << "No\n";
continue;
}
int dis = x2 - x1;
if(dis > (int)mp.size()) {
cout << "No\n";
continue;
}
if(mp.find(x1) == mp.end()) {
cout << "No\n";
continue;
}
auto it = lower_bound(all(mp[x1]), make_pair(y1, 0));
if(it == mp[x1].end()) {
cout << "No\n";
continue;
}
int st = (*it).ss; --dis;
while(dis) {
int tmp = lg[dis];
st = sparse_table[tmp][st];
dis -= pw[tmp];
}
if(st == t) {
cout << "No\n";
continue;
}
pii tmp1 = v[st];
if(tmp1.ss <= y2) {
cout << "Yes\n";
}
else cout << "No\n";
}
}
signed main() {
#ifdef CDuongg
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2004 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
6 ms |
2132 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
5 ms |
1876 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
21020 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
88 ms |
20928 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
114 ms |
20336 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
93 ms |
20928 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
21552 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
219 ms |
21044 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
255 ms |
20820 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
302 ms |
21368 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
305 ms |
21260 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
413 ms |
27388 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1620 KB |
5000 token(s): yes count is 3238, no count is 1762 |
| 2 |
Correct |
6 ms |
1620 KB |
5000 token(s): yes count is 3837, no count is 1163 |
| 3 |
Correct |
12 ms |
2204 KB |
5000 token(s): yes count is 4104, no count is 896 |
| 4 |
Correct |
11 ms |
1732 KB |
5000 token(s): yes count is 3934, no count is 1066 |
| 5 |
Correct |
11 ms |
1876 KB |
5000 token(s): yes count is 3384, no count is 1616 |
| 6 |
Correct |
27 ms |
1772 KB |
5000 token(s): yes count is 3390, no count is 1610 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
421 ms |
28636 KB |
200000 token(s): yes count is 171404, no count is 28596 |
| 2 |
Correct |
370 ms |
23056 KB |
200000 token(s): yes count is 161254, no count is 38746 |
| 3 |
Correct |
226 ms |
20780 KB |
200000 token(s): yes count is 117455, no count is 82545 |
| 4 |
Correct |
626 ms |
40924 KB |
200000 token(s): yes count is 182118, no count is 17882 |
| 5 |
Correct |
419 ms |
28864 KB |
200000 token(s): yes count is 167565, no count is 32435 |
| 6 |
Correct |
242 ms |
21524 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 7 |
Correct |
238 ms |
21412 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 8 |
Correct |
240 ms |
20708 KB |
200000 token(s): yes count is 122100, no count is 77900 |
| 9 |
Correct |
486 ms |
27264 KB |
200000 token(s): yes count is 139670, no count is 60330 |
| 10 |
Correct |
448 ms |
27284 KB |
200000 token(s): yes count is 165806, no count is 34194 |
| 11 |
Correct |
513 ms |
33648 KB |
200000 token(s): yes count is 175646, no count is 24354 |
| 12 |
Correct |
193 ms |
22076 KB |
200000 token(s): yes count is 134695, no count is 65305 |
| 13 |
Correct |
220 ms |
21608 KB |
200000 token(s): yes count is 126733, no count is 73267 |
| 14 |
Correct |
289 ms |
21276 KB |
200000 token(s): yes count is 155290, no count is 44710 |
| 15 |
Correct |
215 ms |
21240 KB |
200000 token(s): yes count is 129674, no count is 70326 |
