제출 #1348652

#제출 시각아이디문제언어결과실행 시간메모리
1348652fatime_aslan_156Trampoline (info1cup20_trampoline)C++20
0 / 100
164 ms52804 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll r,c,n;
    vector<ll>g;
    cin>>r>>c>>n;
    vector<vector<ll>>p(20,vector<ll>(n,-1));
    vector<ll>x(n),y(n);
    for(int i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
        g.push_back(x[i]);
        g.push_back(x[i]+1);
    }
    sort(g.begin(),g.end());
	g.erase(unique(g.begin(),g.end()));
	ll d=g.size();
	vector<array<ll,2>>s[d];
	for(int i=0;i<n;i++)
	{
	    x[i]=lower_bound(g.begin(),g.end(),x[i])-g.begin();
	    s[x[i]].push_back({y[i],i});
	}
	for(int i=0;i<d;i++)
	sort(s[i].begin(),s[i].end());
	for(int i=0;i<n;i++)
	{
	    if(x[i]+1>=d)
	    p[0][i]=-1;
	    else
	    {
	    auto f=lower_bound(s[x[i]+1].begin(),s[x[i]+1].end(),array<ll,2>{y[i],0});
	    if(f==s[x[i]+1].end())
	    p[0][i]=-1;
	    else
	    p[0][i]=(*f)[1];
	    }
	}
	for(int i=1;i<20;i++)
	{
	    for(int j=0;j<n;j++)
	    {
	        if(p[i-1][j]!=-1)
	        p[i][j]=p[i-1][p[i-1][j]];
	    }
	}
	ll q;
	cin>>q;
	while(q--)
	{
	    ll x1,y1,x2,y2;
	    cin>>x1>>y1>>x2>>y2;
	    if(x1>x2 || y1>y2)
	    {
	        cout<<"No"<<endl;
	        continue;
	    }
	    if(x1==x2)
	    {
	        cout<<"Yes"<<endl;
	        continue;
	    }
	    if(!binary_search(g.begin(),g.end(),x1) || !binary_search(g.begin(),g.end(),x2))
	    {
	        cout<<"No"<<endl;
	        continue;
	    }
	    x1=lower_bound(g.begin(),g.end(),x1)-g.begin();
	    x2=lower_bound(g.begin(),g.end(),x2)-g.begin();
	    ll w;
	    auto f=lower_bound(s[x1].begin(),s[x1].end(),array<ll,2>{y1,0});
	    if(f==s[x1].end())
	    w=-1;
	    else
	    w=(*f)[1];
	    ll z=x2-x[w]+1;
	    for(int i=19;i>=0;i--)
	    {
	        if(z&(1<<i))
	        w=p[i][w];
	    }
	    if(w==-1 || y[w]>y2)
	    cout<<"No"<<endl;
	    else
	    cout<<"Yes"<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...