QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#467#266295#7752. The Only Way to the Destinationship2077mendicillin2Failed.2023-11-27 08:30:272023-11-27 08:30:28

Details

Extra Test:

Invalid Input

input:

2 4 2
1 2 3
1 1 4

output:


result:

FAIL white cells are not connected

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#266295#7752. The Only Way to the Destinationmendicillin2#AC ✓23ms10364kbC++171.3kb2023-11-26 11:35:052023-11-26 11:35:06

answer

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

using ll = int64_t;

void NO() {
	cout << "NO" << '\n';
	exit(0);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N, M, K;
	cin >> N >> M >> K;

	if (N == 1) {
		cout << "YES" << '\n';
		exit(0);
	}

	if (M > 3 * K) {
		NO();
	}

	ll nv = ll(N) * M;
	ll ne = 0;

	vector<vector<pair<int, int>>> cols(M);
	for (int k = 0; k < K; k++) {
		int xl, xr, y;
		cin >> xl >> xr >> y;
		xl--, xr--, y--;
		cols[y].emplace_back(xl, xr);

		nv -= (xr-xl+1);
	}

	for (int y = 0; y < M; y++) {
		sort(cols[y].begin(), cols[y].end());

		int prv = 0;
		for (auto [xl, xr] : cols[y]) {
			ne += max(xl - prv - 1, 0);
			prv = xr+1;
		}
		ne += max(N-1 - prv, 0);
	}
	for (int y = 0; y+1 < M; y++) {
		ne += N;

		for (auto [xl, xr] : cols[y]) {
			ne -= (xr-xl+1);
		}
		for (auto [xl, xr] : cols[y+1]) {
			ne -= (xr-xl+1);
		}

		auto it = cols[y+1].begin();
		for (auto [xl, xr] : cols[y]) {
			while (it != cols[y+1].end() && it->second < xl) {
				++it;
			}
			while (it != cols[y+1].end()) {
				int cl = max(it->first, xl);
				int cr = min(it->second, xr);
				if (cl <= cr) {
					ne += (cr-cl+1);
					++it;
				} else {
					break;
				}
			}
			if (it != cols[y+1].begin()) {
				--it;
			}
		}
	}

	cout << (nv == 0 || nv - ne == 1 ? "YES" : "NO") << '\n';

	return 0;
}