답안 #920930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
920930 2024-02-03T08:03:11 Z hmm789 Trampoline (info1cup20_trampoline) C++14
19 / 100
48 ms 4236 KB
#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 || 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--;
		if(memo[it->second][it2->second]) cout << "Yes" << '\n';
		else cout << "No" << '\n';
	}
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 41 ms 4188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 4176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3932 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 6 ms 3996 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 7 ms 4188 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 6 ms 4104 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 7 ms 4236 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 6 ms 4188 KB 5000 token(s): yes count is 3390, no count is 1610
# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 4176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -