Submission #920916

#	Time	Username	Problem	Language	Result	Execution time	Memory
920916		hmm789	Trampoline (info1cup20_trampoline)	C++14	0 / 100	52 ms	6364 KiB

trampoline

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

const int MAXN = 5000;

vector<int> adj[MAXN];

bitset<MAXN> memo[MAXN];
bool v[MAXN];
void dp(int x) {
	if(v[x]) return;
	v[x] = 1;
	memo[x][x] = 1;
	for(int i : adj[x]) {
		dp(i);
		memo[x] |= memo[i];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	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});
	}
	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[i].push_back(it->second);
	}
	for(int i = 0; i < n; i++) dp(i);
	int q;
	cin >> q;
	while(q--) {
		cin >> x1 >> y1 >> x2 >> y2;
		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].upper_bound({y2, 0});
		if(it == m[x1].end()) {
			cout << "No" << '\n';
			continue;
		}
		if(it2 == m[x2-1].begin()) {
			cout << "No" << '\n';
			continue;
		}
		it2--;
		if(memo[it->second][it2->second]) cout << "Yes" << '\n';
		else cout << "No" << '\n';
	}
}

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