Submission #921002

#	Time	Username	Problem	Language	Result	Execution time	Memory
921002		hmm789	Trampoline (info1cup20_trampoline)	C++14	100 / 100	700 ms	72548 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000;

vector<int> adj[MAXN];
int p[MAXN][20], depth[MAXN], grp[MAXN];

void dfs(int x, int g, int d, int par) {
	grp[x] = g;
	depth[x] = d;
	p[x][0] = par;
	for(int i = 1; i < 20; i++) {
		if(p[x][i-1] == -1) break;
		p[x][i] = p[p[x][i-1]][i-1];
	}
	for(int i : adj[x]) if(i != par) dfs(i, g, d+1, x);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	memset(p, -1, sizeof(p));
	int r, c, n, x1, y1, x2, y2;
	cin >> r >> c >> n;
	pair<int, int> a[n];
	for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
	sort(a, a+n);
	//for(int i = 0; i < n-1; i++) if(a[i].first == a[i+1].first) adj[i].push_back(i+1);
	map<int, set<pair<int, int>>> m;
	for(int i = 0; i < n; i++) {
		m[a[i].first].insert({a[i].second, i});
	}
	int tmp[n];
	memset(tmp, 0, sizeof(tmp));
	for(int i = 0; i < n; i++) {
		if(m.find(a[i].first+1) == m.end()) continue;
		auto it = m[a[i].first+1].lower_bound({a[i].second, 0});
		if(it == m[a[i].first+1].end()) continue;
		adj[it->second].push_back(i);
		tmp[i] = 1;
	}
	for(int i = 0; i < n; i++) if(tmp[i] == 0) dfs(i, i, 0, -1);
	int q;
	cin >> q;
	while(q--) {
		cin >> x1 >> y1 >> x2 >> y2;
		if(x1 > x2 || y1 > y2) {
			cout << "No" << '\n';
			continue;
		}
		if(x1 == x2) {
			cout << "Yes" << '\n';
			continue;
		}
		if(m.find(x1) == m.end()) {
			cout << "No" << '\n';
			continue;
		}
		if(m.find(x2-1) == m.end()) {
			cout << "No" << '\n';
			continue;
		}
		auto it = m[x1].lower_bound({y1, 0});
		auto it2 = m[x2-1].lower_bound({y2+1, 0});
		if(it == m[x1].end()) {
			cout << "No" << '\n';
			continue;
		}
		if(it2 == m[x2-1].begin()) {
			cout << "No" << '\n';
			continue;
		}
		it2--;
		int h = x2-1-x1;
		int cur = it->second;
		for(int i = 0; i < 20; i++) {
			if(h&(1<<i)) cur = p[cur][i];
			if(cur == -1) {
				cout << "No" << '\n';
				goto ed;
			}
		}
		if(a[cur].second <= a[it2->second].second) cout << "Yes" << '\n';
		else cout << "No" << '\n';
		ed:;
	}
}

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