Submission #1318379

#TimeUsernameProblemLanguageResultExecution timeMemory
1318379Muhammad_AneeqTrampoline (info1cup20_trampoline)C++20
0 / 100
112 ms26320 KiB
#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 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...