QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#236311 | #1286. Ternary String Counting | le6666 | WA | 1ms | 4016kb | C++14 | 3.0kb | 2023-11-03 20:27:34 | 2023-11-03 20:27:35 |
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) {
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);
}
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;
}
/*
2
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4016kb
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: 1ms
memory: 3944kb
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:
90 0 3 0 46875 57 9 0 14925 3 3 2901 2925 561 24003 27255 3 0 3 3 3 0 9 0 3 3405 165 0 0 0 423 0 9 0 273 9 4089 3 3 3 195 3 3 705 2919 75 3 3 0 0 7347 0 3 3 7779 327 8751 489 9 0 3 3 3 3549 3 3 0 27 0 0 75 2109 3 3 9 31269 0 0 153 4827 3 2163 453 3 219 10899 0 0 3 0 33 165 0 111 3 3 5691 3 8745 3 11...
result:
wrong answer 3rd words differ - expected: '0', found: '3'