Submission #1318421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318421		Faisal_Saqib	Trampoline (info1cup20_trampoline)	C++20	100 / 100	905 ms	103724 KiB

trampoline

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const int LG=21,N=4e6;
int nxt[N][LG];
map<int,int> mp;
pair<int,int> ind[N];
int row[N];
vector<int> hv[N];
vector<pair<int,int>> rg[N];
int ag=1;
int get(int x,int y)
{
	auto& cur=rg[mp[x]];
	// cout<<"At "<<x<<' '<<y<<endl;
	// cout<<mp[x]<<endl;
	// for(auto [p,q]:cur)cout<<p<<' '<<q<<endl;
	// return 0;
	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;
	vector<pair<int,int>> st;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		oc.insert(x);
		oc.insert(x+1);
		st.push_back({x,y});
		// hv[x].push_back(y);
	}
	vector<int> cpp(begin(oc),end(oc));
	reverse(begin(cpp),end(cpp));
	for(int i=0;i<cpp.size();i++)
	{
		mp[cpp[i]]=i; // mp[x] = index of hv and etc
	}
	for(auto [x,y]:st)
	{
		hv[mp[x]].push_back(y);
	}
	int sz=cpp.size();
	for(int i=0;i<sz;i++)sort(begin(hv[i]),end(hv[i]));
	
	for(int idd=0;idd<sz;idd++)
	{
		int x=cpp[idd];
		int lst=0;
		for(auto&y:hv[idd])
		{
			// [lst,y-1]
			if(lst<y)
			{
				nxt[ag][0]=ag+1;
				// cout<<ag<<" represnt "<<x<<' '<<lst<<' '<<y-1<<endl;
				row[ag]=x;
				ind[ag]={x,c+2};
				rg[idd].push_back({y-1,ag});
				ag++;
			}
		// 	cout<<ag<<" represnt "<<x<<' '<<y<<' '<<y<<endl;
			rg[idd].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;
		ind[ag]={x,c+2};
		// cout<<"pushing "<<c+2<<' '<<ag<<' '<<idd<<endl;
		rg[idd].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
				ys=ind[sp].second;
				if(ys<=ye)
				{
					cout<<"Yes"<<endl;
				}
				else{
					cout<<"No"<<endl;
				}
			}
		}
		else{
			cout<<"No"<<endl;
		}
	}
	
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27