#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN=1e9+10;
const ll MAXK=2e5+10;
const ll MAXQ=2e5+10;
const ll MAXLOG=18;
ll n,m,k,q;
pair<ll,ll>v[MAXK];
ll lift[MAXK][MAXLOG];
ll depth[MAXK];
void read()
{
cin>>n>>m>>k;
for(ll i=1;i<=k;i++)
{
ll x,y;
cin>>x>>y;
v[i]=make_pair(x,y);
}
sort(v+1,v+k+1);
}
ll lift_node(ll node,ll k)
{
for(ll i=0;i<MAXLOG;i++)
{
if(k&(1<<i))
{
node=lift[node][i];
}
}
}
ll bin_search(pair<ll,ll>cur)
{
ll left=1,right=k,mid;
while(left<=right)
{
mid=left+(right-left)/2;
if(v[mid]>=cur)
right=mid-1;
else
left=mid+1;
}
return right==k?0:right+1;
}
bool check_ans(pair<ll,ll>ans,ll x,ll y)
{
return ans.first<=x&&ans.second<=y;
}
bool check_query(ll x1,ll y1,ll x2,ll y2)
{
return x1<=x2&&y1<=y2;
}
void query(ll x1,ll y1,ll x2,ll y2)
{
if(!check_query(x1,y1,x2,y2))
{
cout<<"No"<<endl;
///cout<<"hui"<<endl;
return;
}
if(x1==x2)
{
cout<<"Yes"<<endl;
return;
}
pair<ll,ll>cur=make_pair(x1,y1);
ll pos=bin_search(cur);
pair<ll,ll>ans=v[pos];
if(!check_ans(ans,x2,y2))
{
cout<<"No"<<endl;
///cout<<"chep"<<endl;
return;
}
ll diff=x2-x1-1;
if(depth[pos]<diff)
{
cout<<"No"<<endl;
///cout<<"daima"<<endl;
return;
}
ll anspos=lift_node(pos,diff);
if(v[anspos].first<=x2&&v[anspos].second<=y2)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
void fill_lift(ll idx,ll pos)
{
///cout<<"namereno"<<endl;
depth[idx]=depth[pos]+1;
lift[idx][0]=pos;
for(ll j=1;j<MAXLOG;j++)
lift[idx][j]=lift[lift[idx][j-1]][j-1];
}
void prekompot()
{
for(ll i=k;i>0;i--)
{
pair<ll,ll>target=v[i];
target.first++;
ll pos=bin_search(target);
///cout<<pos<<endl;
///cout<<v[pos].first<<" "<<v[pos].second<<endl;
if(v[pos].first==target.first)
fill_lift(i,pos);
}
}
void process_queries()
{
cin>>q;
for(ll i=1;i<=q;i++)
{
ll x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
query(x1,y1,x2,y2);
}
}
void control_print()
{
for(ll i=1;i<=k;i++)
{
cout<<depth[i]<<" ";
}
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
prekompot();
///control_print();
process_queries();
return 0;
}
Compilation message
trampoline.cpp: In function 'll lift_node(ll, ll)':
trampoline.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
40 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
5208 KB |
expected YES, found NO [1st token] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
66 ms |
35140 KB |
expected YES, found NO [3rd token] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
157 ms |
45412 KB |
expected YES, found NO [4th token] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
5720 KB |
expected YES, found NO [1st token] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
154 ms |
45436 KB |
expected YES, found NO [1st token] |
2 |
Halted |
0 ms |
0 KB |
- |