QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#356849 | #1286. Ternary String Counting | james1BadCreeper | WA | 0ms | 3652kb | C++14 | 2.0kb | 2024-03-18 13:52:48 | 2024-03-18 13:52:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
const int P = 1e9 + 7;
inline void add(int &x, int k) { x = (x + k) % P; }
inline void sub(int &x, int k) { x = (x - k + P) % P; }
int n, m;
int mnj[N], mxj[N], mnk[N], mxk[N], f[N][N];
int rs[N], cs[N], tmp[N], lk[N], rk[N];
inline void del(int j, int k) {
sub(rs[j], f[j][k]); sub(cs[k], f[j][k]);
f[j][k] = 0;
}
void solve(void) {
cin >> n >> m;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) f[i][j] = 0;
mnj[i] = mnk[i] = 0, mxj[i] = mxk[i] = n;
rs[i] = cs[i] = 0; lk[i] = 0; rk[i] = n;
}
while (m--) {
int l, r, x; cin >> l >> r >> x;
if (x == 1) mxj[r] = min(mxj[r], l - 1);
else if (x == 2) mnj[r] = max(mnj[r], l), mxk[r] = min(mxk[r], l - 1);
else mnk[r] = max(mnk[r], l);
}
f[0][0] = rs[0] = cs[0] = 1;
int lj = 0;
for (int i = 1; i <= n; ++i) {
if (mnj[i] <= i - 1 && i - 1 <= mxj[i]) {
for (int k = 0; k < i; ++k) tmp[k] = (rs[k] + cs[k]) % P;
for (int k = mnk[i]; k <= min(mxk[i], max(0, i - 2)); ++k) // f[i][i - 1][k]
add(f[i - 1][k], tmp[k]),
add(rs[i - 1], tmp[k]),
add(cs[k], tmp[k]);
}
for (int j = lj; j < i; ++j)
if (j < mnj[i] || j > mxj[i]) {
for (int k = 0; k <= n; ++k) del(j, k);
lk[j] = n; rk[j] = 0;
lj = j + 1;
} else {
for (int k = lk[j]; k < mnk[i]; ++k) del(j, k);
for (int k = mxk[i] + 1; k <= rk[j]; ++k) del(j, k);
lk[j] = max(lk[j], mnk[i]);
rk[j] = min(rk[j], mxk[i]);
}
}
int ans = 0;
for (int i = 0; i <= n; ++i) add(ans, rs[i]);
cout << ans << '\n';
}
int main(void) {
ios::sync_with_stdio(0);
int T; cin >> T;
while (T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 0ms
memory: 3652kb
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 0 0 24300 0 0 0 768 0 0 990 2916 54 6480 864 0 0 21 0 0 0 0 27 9 0 0 0 0 54 96 0 6 0 27 0 0 0 9 0 108 0 0 9 2916 15 0 0 0 0 0 0 0 3 0 486 8748 0 0 0 9 0 0 4437 3 0 9 18 0 9 0 63 0 0 0 126 0 0 0 1992 0 81 537 9 243 1656 3 3 0 0 27 54 0 18 0 0 0 0 756 0 1620 324 0 0 63 54 0 0 90 9 54 0 27 0 0 0 0...
result:
wrong answer 12th words differ - expected: '972', found: '990'