/*
#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[20];
int sparse_table[20][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), sortbysec);
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) {
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) {
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 |
Runtime error |
10 ms |
4052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
21360 KB |
expected NO, found YES [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
21328 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
187 ms |
21568 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
255 ms |
20968 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
247 ms |
21344 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
250 ms |
21440 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
341 ms |
27328 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
3284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
176 ms |
56172 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
