Submission #1009020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009020		PenguinsAreCute	Trampoline (info1cup20_trampoline)	C++17	100 / 100	661 ms	41396 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ii = pair<int,int>;
vector<int> adj[200005];
int pa[200005], h[200005], j[200005];
void dfs(int x) {
	for(auto i: adj[x]) {
		h[i] = h[x] + 1;
		j[i] = (h[j[j[x]]]+h[x]==(h[j[x]]<<1)?j[j[x]]:x);
		dfs(i);
	}
}
int lift(int x, int t) {
	while(h[x]>t) x=(h[j[x]]<t?pa[x]:j[x]);
	return x;
}
main() {
	int r, c, n; cin >> r >> c >> n;
	vector<ii> v;
	for(int x,y,i=0;i<n;i++) {
		cin >> x >> y;
		v.push_back({x,y});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++) {
		auto [x,y] = v[i];
		auto it = lower_bound(v.begin(),v.end(),ii(x+1,y));
		if(it==v.end()||(*it).first>x+1) pa[i]=n;
		else pa[i]=it-v.begin();
		adj[pa[i]].push_back(i);
	}
	j[n] = n; dfs(n);
	int t; cin >> t;
	for(int x1,y1,x2,y2;t--;) {
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1==x2) {
			cout << (y1<=y2?"Yes\n":"No\n");
			continue;
		}
		if(x1>x2) {
			cout << "No\n";
			continue;
		}
		auto it = lower_bound(v.begin(),v.end(),ii(x1,y1));
		if(it==v.end()||(*it).first>x1) {
			cout << "No\n";
			continue;
		}
		int green = it - v.begin();
		if(h[green]<x2-x1-1) {
			cout << "No\n";
			continue;
		}
		int dest = lift(green,h[green]-(x2-x1-1));
		cout << (dest!=n && v[dest].first==x2-1 && v[dest].second<=y2 ? "Yes\n" : "No\n");
	}
}

Compilation message (stderr)

trampoline.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main() {
      | ^~~~

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