QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583738#9372. Prefix of SuffixesTLE_AutomatAC ✓74ms40700kbC++201.8kb2024-09-22 21:45:572024-09-22 21:45:57

Judging History

你现在查看的是测评时间为 2024-09-22 21:45:57 的历史记录

  • [2024-09-23 01:45:22]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:76ms
  • 内存:48760kb
  • [2024-09-22 21:45:57]
  • 评测
  • 测评结果:100
  • 用时:74ms
  • 内存:40700kb
  • [2024-09-22 21:45:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

void solve() {
    int n;
    cin >> n;
    vector s(n + 1, 0), a(n + 1, 0), b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> a[i] >> b[i];
    }

    vector kmp(n + 1, 0);
    vector fa(n + 1, map<int, int>());
    ll ans = 0, lans = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        s[i] = (s[i] + lans) % n;
        int p = kmp[i - 1];
        while (p && s[p + 1] != s[i]) {
            if (!fa[i - 1][s[p + 1]]) {
                fa[i - 1][s[p + 1]] = p;
            }
            p = kmp[p];
        }
        if (i > 1 && s[p + 1] == s[i]) {
            if (!fa[i - 1][s[p + 1]]) {
                fa[i - 1][s[p + 1]] = p;
            }
            kmp[i] = p + 1;
        }

        for (auto [x, y] : fa[p]) {
            if (!fa[i - 1][x]) {
                fa[i - 1][x] = y;
            }
        }

        for (auto [x, y] : fa[i - 1]) {
            if (x == s[i]) {
                continue;
            }
            int u = fa[i - 1][x];
            while (u) {
                sum -= b[i - u];
                u = fa[u][x];
            }
        }
        if (s[i] == s[1]) {
            sum += b[i];
        }

        ans += sum * a[i];
        lans = ans;
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

3
0 1 2
1 2 3
2 3 4

output:

2
12
18

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 62ms
memory: 37812kb

input:

300000
0 656 16
289505 337 134
284112 597 249
125908 340 198
35807 659 432
176485 203 109
34993 630 534
159464 900 189
251564 525 722
243164 591 933
233708 956 818
218412 245 398
214492 487 25
206699 587 984
219699 388 471
30743 20 816
14104 463 222
228887 460 311
3108 721 723
79005 43 882
78317 439...

output:

10496
15888
174093
264193
723516
865007
1640537
2748437
2756837
2766293
2781589
2785509
2793301
3380301
3569257
3585897
3971113
4496893
5320996
5321684
5328708
5331972
5338436
5374847
5408771
5620346
5838121
6584511
6682059
7001091
8582958
8586430
8591102
9349742
9692438
9701110
9701942
9763278
9793...

result:

ok 300000 lines

Test #3:

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

input:

300000
1 710 687
112231 151 233
273311 570 425
106660 563 20
19879 148 305
218203 293 631
16912 714 482
126395 768 498
116315 338 66
293477 755 760
275171 692 666
55151 690 800
137501 982 29
173831 875 240
36956 26 767
19094 39 863
292302 282 289
17070 484 954
282950 411 889
24341 152 925
99180 938 ...

output:

487770
626690
1393340
1780121
1881797
2083088
2573606
3483686
3906524
5424829
6244849
7062499
8226169
9263044
9280906
9307699
9582931
10517051
11675660
12200820
13740078
13905920
13965151
14345749
14922142
15452506
16315308
17334207
18020151
18770944
19847783
20533145
21332020
21426574
22101304
2310...

result:

ok 300000 lines

Test #4:

score: 0
Accepted
time: 68ms
memory: 35568kb

input:

300000
0 342 218
225444 175 812
45194 762 184
20127 331 432
247968 237 403
100792 120 129
74632 113 110
49998 237 155
298331 343 101
188915 408 749
99970 985 443
48885 405 477
187995 622 738
221123 629 412
260618 436 67
234958 539 631
119167 874 524
168547 97 400
147400 354 846
70744 446 27
184159 5...

output:

74556
254806
1179874
1252032
1399209
1425369
1450003
1501669
1611086
1700030
2351115
2812005
3978877
5139382
5765042
6480834
7031454
7052600
7429256
7915842
8035960
8063646
8175698
8472538
8552762
8750706
8966566
9669946
10704433
10738569
10816395
11668000
11883820
11935050
12716145
12770645
1307665...

result:

ok 300000 lines

Test #5:

score: 0
Accepted
time: 74ms
memory: 39124kb

input:

300000
1 599 472
17272 165 190
239393 446 244
220056 323 806
288788 604 743
3700 410 719
110181 537 355
266081 539 470
120328 893 538
298833 902 384
126721 300 398
165721 5 487
160926 755 37
76631 408 29
172223 270 544
197902 548 555
241134 888 723
121999 129 463
1383 800 518
153383 122 995
95800 48...

output:

282728
360608
679944
911212
1196300
1389820
1833919
2279672
2701168
3473280
3734280
3739075
4123370
4327778
4602098
5158866
5578002
5698617
6446617
6504201
6565065
7370245
8883045
10823333
11920153
11941237
12596845
13404317
13908110
15126350
15842750
16335950
16982245
17714115
18205955
18399785
189...

result:

ok 300000 lines

Test #6:

score: 0
Accepted
time: 59ms
memory: 38216kb

input:

300000
1 961 764
165797 639 239
124879 795 175
117500 362 426
286719 285 944
68980 701 287
232228 970 595
91149 991 509
29606 506 622
270735 846 380
93778 601 464
249840 559 668
138234 273 79
69138 834 5
261905 353 632
264327 363 483
82989 47 149
17376 790 109
232246 570 333
96767 600 49
208967 678 ...

output:

734204
1375121
1982501
2413281
2631021
3367772
4108852
5370395
6329265
7406223
8450160
9161767
9530863
10238095
10535674
11017012
11082624
12067754
12503234
12991034
13776158
14210300
14467004
14836573
15172539
16441380
18727362
18962397
19894133
20009497
21243037
23339797
24856697
24969005
25557675...

result:

ok 300000 lines

Test #7:

score: 0
Accepted
time: 55ms
memory: 29168kb

input:

300000
3 383 741
16200 685 25
91487 337 515
141772 711 779
214921 586 275
80693 74 986
25860 460 595
285000 100 71
210901 278 343
4902 424 374
290720 283 109
50170 70 86
284649 765 150
17784 523 250
230241 60 67
185780 90 55
119090 206 104
266446 740 633
149686 987 24
269860 183 331
69290 483 356
11...

output:

283803
808513
1058230
1585081
2019307
2074141
2415001
2489101
2695099
3009283
3249833
3315353
3882218
4269761
4314221
4380911
4533557
5550317
6930143
7130711
7488614
8140694
8806853
9248489
9537965
9706172
10034435
10045550
10522754
11017001
11414177
11562377
11754296
12137032
12342289
12823939
1338...

result:

ok 300000 lines

Test #8:

score: 0
Accepted
time: 73ms
memory: 40700kb

input:

300000
1 776 83
235592 641 187
182389 397 773
149439 616 887
151918 221 36
237549 723 455
148575 697 569
294131 712 146
131082 392 502
41315 687 831
13396 424 158
225861 156 160
187953 265 773
261112 660 943
296152 120 495
193432 675 23
137408 786 292
142657 653 543
197783 330 6
168412 393 956
13343...

output:

64408
117611
150562
748082
962452
1351426
1805870
1968918
2058686
2686604
3074140
3112048
3338888
3903848
4006568
4062593
4357343
4602218
4631588
4666565
5385179
5556918
6086022
6583227
6742567
7140901
7982945
8193883
8204923
8216587
8366275
8736226
8932822
9161803
9593559
9630704
10067132
10611050
...

result:

ok 300000 lines

Test #9:

score: 0
Accepted
time: 55ms
memory: 29976kb

input:

300000
0 6 130
299221 499 412
234352 148 358
215110 821 93
32028 47 506
21546 453 611
285874 764 929
19752 836 710
211069 496 166
64255 377 630
15244 676 620
227363 103 615
150630 897 486
34020 955 775
209868 872 248
180253 512 509
286717 8 307
285678 498 109
220939 509 458
154768 357 216
108357 724...

output:

780
65650
84890
267973
278454
614127
1180251
1288931
1435747
1484757
1572637
1649372
1765982
1890132
2219748
2413284
2414324
2479064
2545234
2591644
2685764
2805624
3567728
3757376
4094528
4427388
4536198
4662948
5149785
5158235
5392757
5497927
5544077
5566177
5591917
5792084
5872034
5957834
6015294...

result:

ok 300000 lines

Test #10:

score: 0
Accepted
time: 62ms
memory: 32216kb

input:

300000
0 499 459
70959 469 519
212278 707 118
187765 471 501
271576 595 830
298470 121 486
184125 881 220
57762 310 738
215472 734 972
178566 828 572
98514 640 916
104754 434 269
205546 762 230
280528 747 447
31936 651 285
156596 626 129
189440 356 691
166905 772 164
112556 57 265
86393 506 846
1541...

output:

229041
687723
1012236
1228425
1501530
1615875
2642240
2784530
3121436
3501488
3795248
3994454
4519472
5368064
6143405
6710561
7033097
7387445
7413608
7645862
7930901
8315033
8389850
8747480
9078878
9466274
10265450
10441247
10721237
11636753
11829533
12053525
12182963
12338105
12417971
12738353
1298...

result:

ok 300000 lines

Test #11:

score: 0
Accepted
time: 54ms
memory: 29508kb

input:

300000
2 748 571
172894 912 718
197325 492 604
216395 728 187
100707 343 97
204852 832 508
29781 934 729
15580 403 643
85468 129 809
207447 946 50
267280 214 593
145088 64 1
108481 356 254
205203 341 467
10493 62 202
262566 27 625
247148 551 721
232528 453 273
273866 842 416
42812 68 223
260532 922 ...

output:

427108
1602676
1883608
2299296
2495149
2970221
4184421
4414534
4592554
5132720
5254914
5291522
5494798
5689509
5737435
5752852
6067473
6326136
7157190
7239470
8026858
8086242
8238128
8408857
9493193
9614816
9786116
9819983
10364079
10587090
11106700
11356798
11469856
11802178
12261262
12326927
12430...

result:

ok 300000 lines

Test #12:

score: 0
Accepted
time: 58ms
memory: 29140kb

input:

300000
2 118 279
267080 249 789
1149 682 492
110871 388 827
2616 392 789
193250 679 108
230478 935 383
269613 994 383
292287 402 322
180126 155 727
136884 561 675
280365 834 958
47677 202 106
291318 896 627
41337 680 797
151616 788 176
93077 544 5
241301 444 116
117424 515 187
177433 100 892
149533 ...

output:

32922
298854
489132
597384
706752
969525
1230390
1507716
1619874
1663119
1819638
2052324
2108682
2358666
2548386
2906926
3058702
3182578
3422568
3450468
3512685
3584323
3598363
3842209
4104469
4312324
4452103
4687276
5761066
6243298
6492445
6542665
6766144
7028962
7067185
7145026
7303498
7516375
776...

result:

ok 300000 lines

Extra Test:

score: 0
Extra Test Passed