QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241453 | #1286. Ternary String Counting | le6666 | WA | 0ms | 3924kb | C++14 | 3.2kb | 2023-11-06 07:51:57 | 2023-11-06 07:51:58 |
Judging History
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) {
// printf("del(%d, %d)\n", x, 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 = 0; 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];
rj[r] = max(rj[r], 1), lj[r] = max(lj[r], 1), rk[r] = max(rk[r], 1), lk[r] = max(lk[r], 1);
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);
}
// bool flag = false;
// for (int i = 1; i <= n; i++)
// if (lj[i] > rj[i] || lk[i] > rk[i])
// flag = true;
// if (flag) { printf("0\n"); continue; }
// 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;
}
/*
4
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
10 4
6 6 1
9 10 2
4 8 3
4 10 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3924kb
input:
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
output:
3 1 0 0 1 0 0 0 0 0 9 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 2 1 0 0 0 0 0 0 27 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ...
result:
wrong answer 2nd words differ - expected: '9', found: '1'