QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#236291#1286. Ternary String Countingle6666WA 2ms5684kbC++142.8kb2023-11-03 20:02:252023-11-03 20:02:26

Judging History

你现在查看的是最新测评结果

  • [2023-11-03 20:02:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5684kb
  • [2023-11-03 20:02:25]
  • 提交

answer

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

const ll MOD = 1e9 + 7;
const int MAXN = 5e3 + 5;
int n, m, lj[MAXN], rj[MAXN], lk[MAXN], rk[MAXN];
struct Limit { int l, r, x; } lim[MAXN];
int nl[MAXN], nr[MAXN];
struct LL {
	ll num = 0;
	LL operator+ (LL other) { return { (num + other.num) % MOD }; }
	LL operator+ (ll k) { return { (num + k) % MOD }; }
	LL operator- (LL other) { return { (num - other.num + MOD) % MOD }; }
	void operator+= (LL other) { *this = *this + other; }
	void operator-= (LL other) { *this = *this - other; }
	LL operator= (ll k) { num = k; return *this; }
};
LL f[MAXN][MAXN], hang[MAXN], lie[MAXN];

void test() {
	for (int i = 0 ; i <= n; i++) {
		for (int j = 0; j <= n; j++) printf("%lld ", f[i][j].num);
		printf("\n");
	}
	printf("\n");
}

void del(int x, int y) {
	if (x || y) hang[x] -= f[x][y], lie[y] -= f[x][y], f[x][y] = 0;
	else if (!x && !y) f[0][0] = 0;
//	else if (!y) lie[0] -= f[x][0], f[x][0] = 0;
}

bool in(int x, int y) { return nl[x] <= y && y <= nr[x]; }

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) scanf("%d%d%d", &lim[i].l, &lim[i].r, &lim[i].x);
		for (int i = 1; i <= n; i++) lj[i] = lk[i] = nl[i] = 0, rj[i] = rk[i] = nr[i] = n;
		for (int i = 0; i <= n; i++) {
			hang[i] = lie[i] = 0;
			for (int j = 0; j <= n; j++)
				f[i][j] = 0;
		}
		for (int i = 1; i <= m; i++) {
			auto [l, r, x] = lim[i];
			if (x == 1) rj[r] = min(rj[r], l - 1);
			else if (x == 2) lj[r] = max(lj[r], l), rk[r] = min(rk[r], l - 1);
			else lk[r] = max(lk[r], l);
		}
//		f[0][0] = hang[0] = lie[0] = 1;
		f[0][0] = 1;
		for (int i = 2; i <= n; i++) {
			if (in(i - 1, 0)) f[i - 1][0] = lie[0] + 1, hang[i - 1] += f[i - 1][0], lie[0] += f[i - 1][0];
			for (int j = 1; j < i - 1; j++) if (in(i - 1, j)) f[i - 1][j] = hang[j] + lie[j];
			for (int j = 1; j < i - 1; j++) hang[i - 1] += f[i - 1][j], lie[j] += f[i - 1][j];
			for (int j = 0; j < lj[i]; j++)
				for ( ; nl[j] <= nr[j]; nl[j]++)
					del(j, nl[j]);
			for (int j = lj[i]; j <= rj[i]; j++) {
				for ( ; nl[j] <= nr[j] && nl[j] < lk[i]; nl[j]++)
					del(j, nl[j]);
				for ( ; nl[j] <= nr[j] && rk[i] < nr[j]; nr[j]--)
					del(j, nr[j]);
			}
			for (int j = rj[i] + 1; j <= n; j++)
				for ( ; nl[j] <= nr[j]; nl[j]++)
					del(j, nl[j]);
//			test();
		}
		ll ans = 0;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				if (i == 0 && j == 0) ans = (ans + f[i][j].num * 3) % MOD;
				else if (i == 0 || j == 0) ans = (ans + f[i][j].num * 6) % MOD;
				else ans = (ans + f[i][j].num * 6) % MOD;
		printf("%lld\n", ans);
//		for (int i = 1; i <= n; i++) {
//			printf("%d %d %d %d\n", lk[i], rk[i], lj[i], rj[i]);
//		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5612kb

input:

4
1 0
2 0
3 0
5 2
1 3 3
4 5 1

output:

3
9
27
18

result:

ok 4 tokens

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 5684kb

input:

741
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3
10 3
9 10 2
3 6 3
1 9 1
3 4
2 3 2
1 3 2
2 3 3
1 3 3
10 4
6 6 1
9 10 2
4 8 3
4 10 3
6 3
1 4 3
2 4 2
2 2 2
4 3
1 4 1
1 1 2
2 3 1
5 3
4 5 2
4 5 1
1 4 3
9 3
2 3 2
1 9 2
2 4 2
4 3
1 3 3
2 3 2
1 2 3
8 4
5 8 1
4 8 1
3 5 3
1 3 3
9 3
4 5 1
1 5 3
3 8 2
8 3
5 7 2...

output:

60
3
3
3
3
3
3
3
1149
3
3
33
1953
3
3093
309
3
3
3
3
3
3
3
3
3
3
3
3
3
3
99
3
3
3
3
9
1461
3
3
3
45
3
3
3
2919
3
3
3
3
3
3
3
3
3
3
3
8751
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1611
3
3
39
3
3
1305
3
3
3
3
3
3
3
9
3
3
3
3
3
3
3
219
3
3
3
3
3
3
3
3
21
3
3
3
3
3
3
3
3
9
813
3
3
3
3
3
3
3
3
3
3
3
...

result:

wrong answer 1st words differ - expected: '90', found: '60'