Submission #3775731

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}

template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}

const int N = 305, INF = 0x3f3f3f3f, ZZQ = 1e9 + 7;

int n, m, min1[N], min2[N], max2[N], max3[N], f[N][N][N], ans;

bool check(int i, int j, int k)
{
	return min1[i] >= j && min2[i] >= k && max2[i] < j && max3[i] < k;
}

int main()
{
	int i, j, k, l, r, x;
	n = read(); m = read();
	For (i, 1, n) min1[i] = min2[i] = INF, max2[i] = max3[i] = -INF;
	while (m--)
	{
		l = read(); r = read(); x = read();
		if (x == 1) min1[r] = Min(min1[r], l);
		else if (x == 2)
			min2[r] = Min(min2[r], l), max2[r] = Max(max2[r], l);
		else max3[r] = Max(max3[r], l);
	}
	f[1][1][0] = max2[1] == -INF && max3[1] == -INF ? 3 : 0;
	For (i, 1, n - 1) For (j, 0, i) For (k, 0, i)
	{
		if (!f[i][j][k]) continue;
		if (check(i + 1, j, k))
			f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % ZZQ;
		if (k)
		{
			if (check(i + 1, i + 1, k))
				f[i + 1][i + 1][k] = (f[i + 1][i + 1][k] + f[i][j][k]) % ZZQ;
			if (check(i + 1, i + 1, j))
				f[i + 1][i + 1][j] = (f[i + 1][i + 1][j] + f[i][j][k]) % ZZQ;
		}
		else
		{
			if (check(i + 1, i + 1, j))
				f[i + 1][i + 1][j] = (2ll * f[i][j][k]
				+ f[i + 1][i + 1][j]) % ZZQ;
		}
	}
	For (j, 0, n) For (k, 0, j - 1)
		ans = (ans + f[n][j][k]) % ZZQ;
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Judge Result