C.涂色（思维）

题解思路

由题目给出的两个涂色条件得出：如果某个格子 是黑色，那么它左上区域 都必须为黑色。

可以转化为：不能出现一个白格子在某个黑格子的左上方（包括正上方或正左方）。

等价条件

设黑格子为 ，白格子为 。 如果 且 ，则白格子在黑格子的左上区域，这是不允许的。

判断方法

直接两两比较黑格子和白格子是 的，不可行。

我们可以按行从小到大，行相同时按列从小到大排序所有格子。 这样在遍历过程中，我们保证当前格子之前的格子要么在同一行但列更小，要么在更小的行。

我们维护一个变量 mn，表示当前已遍历过的白色格子中，最小的列号。

对于当前格子：

• 如果是白色，更新 mn。
• 如果是黑色，检查 mn 是否 ≤ 当前列： 如果是，说明存在一个白格子在它的左上区域（因为白格子的行 ≤ 当前行，且列 mn ≤ 当前列），这是不允许的，输出 。

代码实现

#include<bits/stdc++.h>
using namespace std;
struct node {
	int x, y, c;
}g[200010];
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0; i < k; i++) {
		cin >> g[i].x >> g[i].y >> g[i].c;
	}
	sort(g, g + k, [](node a, node b) {
		if(a.x == b.x) return a.y < b.y;
		return a.x < b.x;
	});
	int mn = INT_MAX;
	for(int i = 0; i < k; i++) {
		if(g[i].c == 0) mn = min(mn, g[i].y);
		else if(mn <= g[i].y) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}