QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356849#1286. Ternary String Countingjames1BadCreeperWA 0ms3652kbC++142.0kb2024-03-18 13:52:482024-03-18 13:52:49

Judging History

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

  • [2024-03-18 13:52:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3652kb
  • [2024-03-18 13:52:48]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'