QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#236291 | #1286. Ternary String Counting | le6666 | WA | 2ms | 5684kb | C++14 | 2.8kb | 2023-11-03 20:02:25 | 2023-11-03 20:02:26 |
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);
}
// 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'