#include <bits/stdc++.h>
using namespace std;
int const N=2e5+10,LG=19;
int ind[N][LG]={};
inline void solve()
{
int n,m,k;
cin>>n>>m>>k;
map<int,vector<pair<int,int>>>vals;
vector<pair<int,int>>ed;
for (int i=0;i<k;i++)
{
int x,y;
cin>>x>>y;
ed.push_back({x,y});
}
for (auto& [i,j]:vals)
sort(begin(j),end(j));
sort(begin(ed),end(ed));
for (int i=0;i<k;i++)
{
int x=ed[i].first,y=ed[i].second;
vals[x].push_back({y,i});
}
for (int i=0;i<k;i++)
{
int f=ed[i].first+1;
int inds=i;
if (vals.find(f)!=vals.end())
{
pair<int,int>g={ed[i].second,0};
int z=lower_bound(begin(vals[f]),end(vals[f]),g)-begin(vals[f]);
if (z!=vals[f].size())
inds=vals[f][z].second;
}
ind[i][0]=inds;
}
for (int i=1;i<LG;i++)
for (int j=0;j+(1<<i)-1<n;j++)
ind[j][i]=ind[ind[j][i-1]][i-1];
int q;
cin>>q;
while (q--)
{
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
if (x1==x2&&y1<=y2)
{
cout<<"Yes\n";continue;
}
if (x2<x1||y2<y1)
{
cout<<"No\n";continue;
}
int df=x2-x1-1;
int ans=-1;
if (vals.find(x1)!=vals.end())
{
pair<int,int>g={y1,0};
int z=lower_bound(begin(vals[x1]),end(vals[x1]),g)-begin(vals[x1]);
if (z!=vals[x1].size())
{
int st=vals[x1][z].second;
for (int i=0;i<LG;i++)
{
if ((1<<i)&df)
st=ind[st][i];
}
ans=st;
}
}
if (ans!=-1&&(ed[ans].first==x2-1&&ed[ans].second<=y2))
{
cout<<"Yes\n";continue;
}
cout<<"No\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
| # | 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... |