Submission #1008847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008847		emptypringlescan	Trampoline (info1cup20_trampoline)	C++17	100 / 100	243 ms	30408 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int r,c,n;
	cin >> r >> c >> n;
	vector<pair<int,int> > grr; 
	vector<pair<int,int> >::iterator it;
	for(int i=0; i<n; i++){
		int x,y;
		cin >> x >> y;
		grr.push_back({x,y});
	}
	sort(grr.begin(),grr.end());
	int par[20][n];
	memset(par,-1,sizeof(par));
	for(int i=0; i<n; i++){
		it=lower_bound(grr.begin(),grr.end(),make_pair(grr[i].first+1,grr[i].second));
		if(it!=grr.end()&&it->first==grr[i].first+1){
			par[0][i]=it-grr.begin();
		}
	}
	for(int i=1; i<20; i++){
		for(int j=0; j<n; j++){
			if(par[i-1][j]==-1) continue;
			par[i][j]=par[i-1][par[i-1][j]];
		}
	}
	int q;
	cin >> q;
	while(q--){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		if(a>c){
			cout << "No\n";
			continue;
		}
		else if(a==c){
			if(b>d) cout << "No\n";
			else cout << "Yes\n";
			continue;
		}
		it=lower_bound(grr.begin(),grr.end(),make_pair(a,b));
		if(it==grr.end()||it->first!=a){
			cout << "No\n";
			continue;
		}
		int cur=it-grr.begin();
		for(int i=19; i>=0; i--){
			if(par[i][cur]==-1) continue;
			if(grr[par[i][cur]].first<c) cur=par[i][cur];
		}
		if(grr[cur].first==c-1&&grr[cur].second<=d) cout << "Yes\n";
		else cout << "No\n";
	}
}

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