记录编号	599692	评测结果	AAAAAAAAAA
题目名称	[CEOI 1999] 奇偶性游戏	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2025-03-25 20:06:18	内存使用	3.60 MiB

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXM = 5e3 + 10;

struct {
	int l, r, ans;
} query[MAXM];

int n, m;
int discrete[MAXM << 1], discnt;
int fa[MAXM << 1];

int find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

int main() {
	freopen("parity.in", "r", stdin);
	freopen("parity.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		char str[10];
		scanf("%d %d %s", &query[i].l, &query[i].r, str);
		query[i].ans = (str[0] == 'o' ? 1 : 0);
		discrete[++discnt] = query[i].l - 1;
		discrete[++discnt] = query[i].r;
	}
	sort(discrete + 1, discrete + discnt + 1);
	n = unique(discrete + 1, discrete + discnt + 1) - discrete - 1;
	
	for (int i = 1; i <= n * 2; ++i) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		int x = lower_bound(discrete + 1, discrete + n + 1, query[i].l - 1) - discrete;
		int y = lower_bound(discrete + 1, discrete + n + 1, query[i].r) - discrete;
		int x_odd = x, x_even = x + n;
		int y_odd = y, y_even = y + n;
		if (query[i].ans == 0) {
			if (find(x_odd) == find(y_even)) {
				printf("%d\n", i - 1);
				return 0;
			}
			fa[find(x_odd)] = find(y_odd);
			fa[find(x_even)] = find(y_even);
		} else {
			if (find(x_odd) == find(y_odd)) {
				printf("%d\n", i - 1);
				return 0;
			}
			fa[find(x_odd)] = find(y_even);
			fa[find(x_even)] = find(y_odd);
		}
	}
	printf("%d\n", m);
	return 0;
}