/***Farhan132***/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast,fast-math")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
const ll mod = (ll) 998244353;
//const ll mod = (ll) 1e9 + 7;
const ll maxn = (ll)1e8 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = (ll)1e18;
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};
bool USACO = 0;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 2e5 + 5;
vector < ii > v[N];
ll par[N][20];
ll x[N], y[N];
void solve(){
ll r, c; cin >> r >> c;
ll n , t; cin >> n;
vector < ll > idx;
y[0] = c + 1;
for(ll i = 1; i <= n; i++){
cin >> x[i] >> y[i];
idx.pb(x[i]);
}
sort(idx.begin(), idx.end());
idx.erase(unique(idx.begin(), idx.end()), idx.end());
for(ll i = 1; i <= n; i++){
ll k = lower_bound(idx.begin(), idx.end(), x[i]) - idx.begin();
v[k].pb({y[i], i});
}
for(ll i = 0; i < idx.size(); i++){
sort(v[i].begin(), v[i].end());
}
mem(par, 0);
for(ll i = 1; i <= n; i++){
ll k = lower_bound(idx.begin(), idx.end(), x[i] + 1) - idx.begin();
if(k == idx.size() || idx[k] != x[i] + 1){
par[i][0] = 0;
}else{
if(v[k].back().ff < y[i]) par[i][0] = 0;
else{
auto [d , j] = *lower_bound(v[k].begin(), v[k].end(), make_pair(y[i], 0LL) );
par[i][0] = j;
}
}
}
for(ll j = 1; j < 20; j++){
for(ll i = 1; i <= n; i++){
par[i][j] = par[par[i][j - 1]][j - 1];
}
}
cin >> t;
while(t--){
ll a, b, c, d;
cin >> a >> b >> c >> d;
if(a > c || b > d){
cout << "No\n";
continue;
}
if(a == c){
cout << "Yes\n";
continue;
}
ll k = lower_bound(idx.begin(), idx.end(), a) - idx.begin();
if(k == idx.size() || idx[k] != a || v[k].back().ff < b){
cout << "No\n";
continue;
}
auto [A , cur] = *lower_bound(v[k].begin(), v[k].end(), make_pair(b, 0LL));
ll tot = c - a - 1;
for(ll i = 19; i >= 0; i--){
if((1LL << i) & tot){
cur = par[cur][i];
}
}
if(y[cur] <= d){
cout << "Yes\n";
}else{
cout << "No\n";
}
}
return;
}
int main() {
#ifdef LOCAL
freopen("in", "r", stdin);
freopen("out", "w", stdout);
auto start_time = clock();
#else
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#endif
//pre(N);
ll T = 1, CT = 0; //cin >> T;
while(T--){
// cout << "Case #" << ++CT <<": " ;
solve();
}
#ifdef LOCAL
auto end_time = clock();
cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n";
#endif
return 0;
}
Compilation message
trampoline.cpp: In function 'void solve()':
trampoline.cpp:93:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(ll i = 0; i < idx.size(); i++){
| ~~^~~~~~~~~~~~
trampoline.cpp:101:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if(k == idx.size() || idx[k] != x[i] + 1){
| ~~^~~~~~~~~~~~~
trampoline.cpp:129:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | if(k == idx.size() || idx[k] != a || v[k].back().ff < b){
| ~~^~~~~~~~~~~~~
trampoline.cpp: In function 'int main()':
trampoline.cpp:164:15: warning: unused variable 'CT' [-Wunused-variable]
164 | ll T = 1, CT = 0; //cin >> T;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
36820 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
22 ms |
36908 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
20 ms |
36752 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
48412 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
171 ms |
48320 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
163 ms |
47052 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
162 ms |
48380 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
268 ms |
58720 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
278 ms |
58668 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
266 ms |
57752 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
298 ms |
58384 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
280 ms |
58352 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
346 ms |
58524 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
36820 KB |
5000 token(s): yes count is 3238, no count is 1762 |
| 2 |
Correct |
20 ms |
36896 KB |
5000 token(s): yes count is 3837, no count is 1163 |
| 3 |
Correct |
20 ms |
36908 KB |
5000 token(s): yes count is 4104, no count is 896 |
| 4 |
Correct |
21 ms |
36824 KB |
5000 token(s): yes count is 3934, no count is 1066 |
| 5 |
Correct |
21 ms |
36804 KB |
5000 token(s): yes count is 3384, no count is 1616 |
| 6 |
Correct |
20 ms |
36892 KB |
5000 token(s): yes count is 3390, no count is 1610 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
476 ms |
58700 KB |
200000 token(s): yes count is 171404, no count is 28596 |
| 2 |
Correct |
395 ms |
58620 KB |
200000 token(s): yes count is 161254, no count is 38746 |
| 3 |
Correct |
325 ms |
57976 KB |
200000 token(s): yes count is 117455, no count is 82545 |
| 4 |
Correct |
537 ms |
59616 KB |
200000 token(s): yes count is 182118, no count is 17882 |
| 5 |
Correct |
357 ms |
58020 KB |
200000 token(s): yes count is 167565, no count is 32435 |
| 6 |
Correct |
342 ms |
58660 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 7 |
Correct |
302 ms |
58660 KB |
200000 token(s): yes count is 156797, no count is 43203 |
| 8 |
Correct |
305 ms |
58100 KB |
200000 token(s): yes count is 122100, no count is 77900 |
| 9 |
Correct |
480 ms |
58480 KB |
200000 token(s): yes count is 139670, no count is 60330 |
| 10 |
Correct |
501 ms |
58640 KB |
200000 token(s): yes count is 165806, no count is 34194 |
| 11 |
Correct |
546 ms |
58740 KB |
200000 token(s): yes count is 175646, no count is 24354 |
| 12 |
Correct |
275 ms |
58908 KB |
200000 token(s): yes count is 134695, no count is 65305 |
| 13 |
Correct |
282 ms |
59040 KB |
200000 token(s): yes count is 126733, no count is 73267 |
| 14 |
Correct |
355 ms |
58532 KB |
200000 token(s): yes count is 155290, no count is 44710 |
| 15 |
Correct |
277 ms |
58372 KB |
200000 token(s): yes count is 129674, no count is 70326 |
