Submission #1318619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318619		MuhammadSaram	Trampoline (info1cup20_trampoline)	C++20	100 / 100	1297 ms	66928 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define mp make_pair

const int M = 2e5 + 1, lg = 18;

int nxt[M][lg];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int r,c,n;
	cin>>r>>c>>n;
	map<int,set<int>> mp;
	set<int> se;
	map<pair<int,int>,int> ind;
	int a[n],b[n]; 
	for (int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
		mp[a[i]].insert(b[i]);
		se.insert(a[i]);
		ind[{a[i],b[i]}]=i;
	}
	for (int i:se)
	{
		bool b=se.count(i+1);
		for (int j:mp[i])
		{
			int id=ind[{i,j}];
			if (b)
			{
				auto it=mp[i+1].lower_bound(j);
				if (it!=mp[i+1].end())
					nxt[id][0]=ind[{i+1,*it}];
				else
					nxt[id][0]=id;
			}
			else nxt[id][0]=id;
		}
	}
	for (int p=1;p<lg;p++)
		for (int i=0;i<n;i++)
			nxt[i][p]=nxt[nxt[i][p-1]][p-1];
	int q;
	cin>>q;
	while (q--)
	{
		int x,y,x1,y1;
		cin>>x>>y>>x1>>y1;
		if (x==x1)
			cout<<(y<=y1?"Yes":"No")<<endl;
		else
		{
			if (!se.count(x) or x1<x)
			{
				cout<<"No"<<endl;
				continue;
			}
			auto it=mp[x].lower_bound(y);
			if (it==mp[x].end())
			{
				cout<<"No"<<endl;
				continue;
			}
			int id=ind[{x,*it}];
			for (int p=29;p>=0;p--)
				if ((x1-x-1)>>p&1)
					id=nxt[id][p];
			if (a[id]==x1-1 && b[id]<=y1)
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
		}
	}

	return 0;
}

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