oj.uz

Submission #920930

# Submission time Handle Problem Language Result Execution time Memory
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';
	}
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 4188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 4176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory 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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 4176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -