#include <bits/stdc++.h>
using namespace std;
#define int long long
map<pair<int,int>, vector<pair<int,int>>> twok;
//~ pair<int,int> par(pair<int,int> c){
//~ if(p[c].first==0){
//~ return c;
//~ }
//~ return p[c]=par(p[c]);
//~ }
pair<int,int> kpar(pair<int,int> c, int k){
for(int i=0;i<20;i++){
if(1<<i & k){
c=twok[c][i];
}
}
return c;
}
signed main(){
int r,c,n;
cin>>r>>c>>n;
map<int,vector<int>> rs;
vector<pair<int,int>> g;
for(int i=0;i<n;i++){
int a,b;cin>>a>>b;
rs[a].push_back(b);
g.push_back({a,b});
}
for(auto & it : rs){
sort(it.second.begin(),it.second.end());
}
for(auto & it : rs){
int x=it.first;
for(auto y:it.second){
//~ printf("at %lld %lld \n",x,y);
fflush(stdout);
auto nxt=lower_bound(rs[x+1].begin(),rs[x+1].end(),y);
if(nxt != rs[x+1].end()){
//~ printf("points to %lld %lld\n",x+1, (*nxt));
//~ fflush(stdout);
twok[{x,y}].push_back({x+1, (*nxt)});
}
}
}
for(auto [x,y]:g){
if((int)twok[{x,y}].size() < 20)twok[{x,y}].resize(20);
}
for(int i=1;i<20;i++){
for(auto [x,y]:g){
//~ printf("calculating 2^%lld par of %lld %lld\n",i,x,y);
pair<int,int> fpar=twok[{x,y}][i-1];
//~ printf("calculating 2^%lld par of %lld %lld, fpar is %lld %lld\n",i,x,y,fpar.first,fpar.second);
//~ fflush(stdout);
if(fpar.first==0) continue;
else twok[{x,y}][i]=twok[fpar][i-1];
//~ printf("done with %lld %lld\n", x,y);
//~ fflush(stdout);
}
}
int t;cin>>t;
for(int i=0;i<t;i++){
int sx, sy, nx, ny;cin>>sx>>sy>>nx>>ny;
if(sx == nx){
cout<<"Yes\n";
continue;
}
pair<int,int> st={sx, 1e15};
auto it=lower_bound(rs[sx].begin(),rs[sx].end(),sy);
if(it==rs[sx].end()){
cout<<"No\n";
continue;
}
st.second=(*it);
st=kpar(st, nx-sx-1);
if(st.first==0){
cout<<"No\n";
}
else {
if(st.second <= ny){
cout<<"Yes\n";
}
else cout<<"No\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |