제출 #1318404

#제출 시각아이디문제언어결과실행 시간메모리
1318404Faisal_SaqibTrampoline (info1cup20_trampoline)C++20
62 / 100
2096 ms101648 KiB
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int R=3000,LG=21,N=1e6;
int nxt[N][LG];
map<int,pair<int,int>> ind;
map<int,int> row;
map<int,vector<int>> hv;
map<int,vector<pair<int,int>>>rg;
int ag=1;
int get(int x,int y)
{
	auto& cur=rg[x];
	return lower_bound(begin(cur),end(cur),make_pair(y,-1))->second;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int r,c,n;
	cin>>r>>c>>n;
	set<int> oc;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		oc.insert(x);
		oc.insert(x+1);
		hv[x].push_back(y);
	}
	for(auto i:oc)sort(begin(hv[i]),end(hv[i]));
	vector<int> cpp(begin(oc),end(oc));
	reverse(begin(cpp),end(cpp));
// 	for(auto x:cpp)
	for(auto x:cpp)
	{
		int lst=0;
		for(auto y:hv[x])
		{
			// [lst,y-1]
			if(lst<y)
			{
				nxt[ag][0]=ag+1;
				// cout<<ag<<" represnt "<<x<<' '<<lst<<' '<<y-1<<endl;
				row[ag]=x;
				rg[x].push_back({y-1,ag});
				ag++;
			}
		// 	cout<<ag<<" represnt "<<x<<' '<<y<<' '<<y<<endl;
			rg[x].push_back({y,ag});
			row[ag]=x;
			ind[ag]={x,y};
			int nt=get(x+1,y);
		// 	cout<<ag<<" edge to "<<nt<<endl;
			nxt[ag][0]=nt;
			ag++;
			lst=y+1;
		}
		// cout<<ag<<" represnt "<<x<<' '<<lst<<' '<<c+2<<endl;
		nxt[ag][0]=ag; // end of row thus made it cyc
		row[ag]=x;
		rg[x].push_back({c+2,ag});
		ag++;
	}
	for(int j=1;j<LG;j++)
	{
	  for(int i=1;i<=ag;i++)
	  {
	    nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	  }
	}
	int t;
	cin>>t;
	while(t--)
	{
		int xs,ys,xe,ye;
		cin>>xs>>ys>>xe>>ye;
		if(xs<=xe and ys<=ye)
		{
			if(xe-xs > n)
			{
				cout<<"No"<<endl;
			}
			else if(xs==xe)
			{
				// same row
				if(ys<=ye)
				{
					cout<<"Yes"<<endl;
				}
				else{
					cout<<"No"<<endl;
				}
			}
			else{
				int sp=get(xs,ys);
				// cout<<"starting "<<sp<<endl;
				for(int j=LG-1;j>=0;j--)
				{
					if(row[nxt[sp][j]]<xe)
					{
						sp=nxt[sp][j];
					}
				}
				// cout<<"ending "<<sp<<endl;
				// sp is not a G or end of row
				if(ind.find(sp)!=ind.end())
				{
					ys=ind[sp].second;
					if(ys<=ye)
					{
						cout<<"Yes"<<endl;
					}
					else{
						cout<<"No"<<endl;
					}
				}
				else{
					cout<<"No"<<endl;
				}
			}
		}
		else{
			cout<<"No"<<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...