QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356848#1286. Ternary String Countingjames1BadCreeperTL 247ms101652kbC++142.0kb2024-03-18 13:51:472024-03-18 13:51:47

Judging History

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

  • [2024-03-18 13:51:47]
  • 评测
  • 测评结果:TL
  • 用时:247ms
  • 内存:101652kb
  • [2024-03-18 13:51:47]
  • 提交

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; 
            } 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: 1ms
memory: 3716kb

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: 0
Accepted
time: 2ms
memory: 3764kb

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
972
2916
0
6480
864
0
0
0
0
0
0
0
0
6
0
0
0
0
0
96
0
6
0
0
0
0
0
0
0
108
0
0
0
2916
0
0
0
0
0
0
0
0
0
0
324
8748
0
0
0
0
0
0
4320
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
1992
0
0
450
0
162
1656
0
0
0
0
0
54
0
18
0
0
0
0
744
0
1620
324
0
0
36
36
0
0
60
6
54
0
0
0
0
0
0
0
0
243
810...

result:

ok 741 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

332
17 5
4 9 1
4 6 1
7 17 1
5 5 1
5 6 3
13 5
10 12 3
8 13 2
1 10 3
2 9 1
9 10 1
19 5
11 13 1
9 17 2
1 7 1
4 4 2
3 9 1
15 4
8 11 2
9 14 3
10 12 2
4 5 2
12 4
3 9 2
7 8 1
1 7 3
6 7 3
16 5
4 14 3
1 5 1
2 10 1
2 12 3
6 9 3
20 4
10 17 3
4 20 3
17 19 3
8 17 1
20 5
11 11 1
9 13 1
1 5 3
17 17 3
3 18 3
17 5
1...

output:

0
0
0
2047032
0
0
0
0
0
839808
0
0
0
0
0
0
0
0
0
0
0
0
44641044
0
20412
0
0
0
0
0
0
0
6
0
0
0
0
81
0
0
0
0
0
0
0
0
0
0
0
313155072
0
0
0
0
0
0
0
0
0
5400
0
10368
0
0
0
0
14580
0
0
0
217728
40310784
0
0
218700
0
0
0
0
1620
0
0
0
0
0
108
146304
0
0
0
466560
288
0
0
0
0
0
0
0
276138
0
0
0
0
0
0
0
52488...

result:

ok 332 tokens

Test #4:

score: 0
Accepted
time: 51ms
memory: 24484kb

input:

5
1000 0
1000 5
779 779 2
543 840 3
30 477 1
10 295 3
463 741 1
1000 6
379 569 1
249 826 2
194 819 3
90 400 1
614 808 2
102 868 2
1000 8
463 981 1
680 857 3
560 623 1
209 659 1
55 957 2
244 327 1
321 888 3
37 204 3
1000 5
336 851 3
410 676 1
522 911 2
165 962 1
258 330 3

output:

56888193
0
0
0
0

result:

ok 5 tokens

Test #5:

score: 0
Accepted
time: 46ms
memory: 24212kb

input:

5
1000 9
190 765 1
212 745 3
437 798 3
682 814 3
122 289 1
44 821 1
115 448 3
400 936 2
562 639 3
1000 5
561 808 3
23 160 2
57 915 2
211 943 3
125 596 2
1000 1
398 739 2
1000 3
629 973 2
7 721 2
591 815 2
1000 10
536 708 1
217 256 2
690 913 3
418 871 2
302 325 2
334 830 2
496 573 2
396 865 1
240 837...

output:

0
0
722271060
85306976
0

result:

ok 5 tokens

Test #6:

score: 0
Accepted
time: 57ms
memory: 42952kb

input:

2
2000 1
1501 1703 2
2000 5
1230 1521 3
1022 1939 3
1241 1283 3
767 1944 2
303 1163 3

output:

841960641
0

result:

ok 2 tokens

Test #7:

score: 0
Accepted
time: 61ms
memory: 43596kb

input:

2
2000 2
640 1942 1
1473 1917 3
2000 4
490 887 1
670 1163 3
824 1434 2
1221 1746 1

output:

0
0

result:

ok 2 tokens

Test #8:

score: 0
Accepted
time: 247ms
memory: 101580kb

input:

1
5000 9
2821 3377 2
798 1535 2
3563 4161 3
2205 2946 3
1320 1594 3
278 1624 1
1243 2759 3
2882 4939 1
2639 3559 3

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 200ms
memory: 101636kb

input:

1
5000 2
539 4252 1
906 3821 1

output:

101862333

result:

ok "101862333"

Test #10:

score: 0
Accepted
time: 0ms
memory: 5896kb

input:

111
34 0
30 0
18 0
35 0
3 0
43 0
13 0
28 0
57 0
75 0
31 0
4 0
92 0
1 0
53 0
85 0
74 0
43 0
59 0
72 0
79 0
40 0
70 0
36 0
86 0
56 0
53 0
66 0
50 0
100 0
60 0
74 0
50 0
51 0
92 0
49 0
50 0
78 0
95 0
4 0
59 0
44 0
92 0
84 0
7 0
75 0
99 0
56 0
54 0
13 0
27 0
33 0
22 0
80 0
14 0
79 0
29 0
39 0
21 0
97 0
...

output:

582926302
130653412
387420489
748778899
27
738321955
1594323
792294829
998064805
100094381
391960236
81
587240675
3
172815616
473062299
700031465
738321955
982583189
966670169
107644805
953271190
662963356
246336683
419186890
666021604
172815616
909419307
710104287
886041711
947749553
700031465
7101...

result:

ok 111 tokens

Test #11:

score: 0
Accepted
time: 4ms
memory: 12404kb

input:

16
350 0
453 0
485 0
361 0
498 0
149 0
433 0
435 0
279 0
240 0
166 0
152 0
393 0
159 0
219 0
222 0

output:

378029361
68761795
621961191
766744305
24977444
679213660
705815658
352340880
186665231
458529104
150230246
338768694
907169137
887128598
322586612
709838468

result:

ok 16 tokens

Test #12:

score: 0
Accepted
time: 84ms
memory: 101652kb

input:

1
5000 0

output:

22443616

result:

ok "22443616"

Test #13:

score: -100
Time Limit Exceeded

input:

1
5000 1000000
4736 4854 3
405 1465 3
835 4720 3
633 1954 3
2182 4257 3
1920 3098 3
302 3157 3
63 3964 3
4032 4116 3
734 1980 3
1083 4515 3
44 4768 3
20 4466 3
1160 2774 3
794 1531 3
2301 4714 3
255 4939 3
2699 2967 3
1835 2733 3
582 2071 3
430 1857 3
249 2013 3
922 4833 3
13 1973 3
3150 3812 3
2904...

output:


result: