Submission #1145145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145145		Halym2007	Trampoline (info1cup20_trampoline)	C++17	100 / 100	245 ms	19220 KiB

trampoline

/*
Note

 I think it is possible to solve for full with kind of LCA
*/


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
const int LOG = 21;
pii p[N];
int n, m, k, q, dp[N][LOG];

//map <int, int> m1, m2;
	
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= k; ++i) {
		cin >> p[i].ff >> p[i].ss;
	}
	sort (p + 1, p + k + 1);
	
	for (int i = 1; i <= k; ++i) {
		auto tr = lower_bound (p + 1, p + k + 1, make_pair(p[i].ff + 1, p[i].ss)) - p;
		if (tr == k + 1) {
			dp[i][0] = i;
		}
		else {
			dp[i][0] = tr;
		}
	}
	for (int j = 1; j < LOG; ++j) {
		for (int i = 1; i <= k; ++i) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}
	
 	cin >> q;
	while ( q-- ) {
		int x, y, x1, y1;
		cin >> x >> y >> x1 >> y1;
		if (x1 < x or y1 < y) {
			cout << "No\n";
			continue;
		}
		if (x1 - x > k) {
			cout << "No\n";
			continue;
		}
		int git = x1 - x - 1;
		if (git < 0) {
			cout << "Yes\n";
			continue;
		}		
		auto tr = lower_bound (p + 1, p + k + 1, make_pair(x, y)) - p;
		if (tr == k + 1 or p[tr].ff != x) {
			cout << "No\n";
			continue;
		}
		x = tr;
//		cout << x << " " << git << " " << dp[1][0] << "\n";
		for (int i = LOG - 1; i >= 0; i--) {
			if (git>>i&1) {
				x = dp[x][i];
			}
		}
//		cout << "\n" << x << "\n";
		if (p[x].ff == x1 - 1 and p[x].ss <= y1) {
			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