/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option
#include<bits/stdc++.h>
using namespace std;
#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 300005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;
map<int, vii> mp;
int jp[maxN][32];
int h[maxN], pl[maxN];
signed main(){
// freopen(".inp", "r", stdin);
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> x >> x >> n;
for1(i, 1, n){
cin >> x >> y;
mp[x].pb(ii(y, i));
h[i] = x;
pl[i] = y;
}
memset(jp, 0, sizeof(jp));
for(auto &pr : mp) sort(all(pr.se));
for(auto &pr : mp){
if(mp.find(pr.fi + 1) == mp.end()) continue;
vii &cac = mp[pr.fi + 1];
for(ii cc : pr.se){
int id = lower_bound(all(cac), ii(cc.fi, -oo))
- cac.begin();
if(id == cac.size()) continue;
jp[cc.se][0] = cac[id].se;
}
}
for1(ds, 0, 25){
for1(i, 0, n){
jp[i][ds + 1] = jp[jp[i][ds]][ds];
}
}
int o; cin >> o; while(o--){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if(x1 >= x2){
if(y1 <= y2 && x1 == x2) cout << "Yes\n";
else cout << "No\n";
continue;
}
vii &cac = mp[x1];
int id = lower_bound(all(cac), ii(y1, -oo)) - cac.begin();
if(id == cac.size()){
cout << "No\n"; continue;
}
id = cac[id].se;
int mask = x2 - x1 - 1;
for2(i, 25, 0) if(mask & (1 << i)){
id = jp[id][i];
}
if(id && pl[id] <= y2) cout << "Yes\n";
else cout << "No\n";
// cout << id << endl;
}
}
Compilation message
trampoline.cpp: In function 'int main()':
trampoline.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(id == cac.size()) continue;
| ~~~^~~~~~~~~~~~~
trampoline.cpp:76:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(id == cac.size()){
| ~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
75860 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
33 ms |
75912 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
29 ms |
75732 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
84448 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
148 ms |
84396 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
146 ms |
83000 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
143 ms |
84236 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
268 ms |
83884 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
286 ms |
83108 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
253 ms |
83128 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
292 ms |
84464 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
293 ms |
84420 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
424 ms |
89752 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
75692 KB |
5000 token(s): yes count is 3238, no count is 1762 |
| 2 |
Correct |
34 ms |
75624 KB |
5000 token(s): yes count is 3837, no count is 1163 |
| 3 |
Correct |
35 ms |
76024 KB |
5000 token(s): yes count is 4104, no count is 896 |
| 4 |
Correct |
38 ms |
75668 KB |
5000 token(s): yes count is 3934, no count is 1066 |
| 5 |
Correct |
34 ms |
75756 KB |
5000 token(s): yes count is 3384, no count is 1616 |
| 6 |
Correct |
33 ms |
75624 KB |
5000 token(s): yes count is 3390, no count is 1610 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
539 ms |
90996 KB |
200000 token(s): yes count is 171404, no count is 28596 |
| 2 |
Correct |
411 ms |
86604 KB |
200000 token(s): yes count is 161254, no count is 38746 |
| 3 |
Correct |
288 ms |
83292 KB |
200000 token(s): yes count is 117455, no count is 82545 |
| 4 |
Correct |
673 ms |
101344 KB |
200000 token(s): yes count is 182118, no count is 17882 |
| 5 |
Correct |
509 ms |
89152 KB |
200000 token(s): yes count is 167565, no count is 32435 |
| 6 |
Correct |
324 ms |
83656 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 7 |
Correct |
334 ms |
83796 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 8 |
Correct |
344 ms |
83104 KB |
200000 token(s): yes count is 122100, no count is 77900 |
| 9 |
Correct |
604 ms |
89844 KB |
200000 token(s): yes count is 139670, no count is 60330 |
| 10 |
Correct |
551 ms |
90288 KB |
200000 token(s): yes count is 165806, no count is 34194 |
| 11 |
Correct |
671 ms |
95332 KB |
200000 token(s): yes count is 175646, no count is 24354 |
| 12 |
Correct |
287 ms |
82572 KB |
200000 token(s): yes count is 134695, no count is 65305 |
| 13 |
Correct |
304 ms |
83508 KB |
200000 token(s): yes count is 126733, no count is 73267 |
| 14 |
Correct |
315 ms |
84344 KB |
200000 token(s): yes count is 155290, no count is 44710 |
| 15 |
Correct |
283 ms |
82868 KB |
200000 token(s): yes count is 129674, no count is 70326 |
