QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#582532 | #9372. Prefix of Suffixes | hhhyh | AC ✓ | 151ms | 24068kb | C++23 | 1.6kb | 2024-09-22 16:46:02 | 2024-09-22 16:46:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i64 = long long;
const int N = 3e5 + 10;
int S[N], A[N], B[N];
int nx[N], val[N];
#define all(x) x.begin(), x.end()
void solve()
{
int n;
cin >> n;
i64 ans = 0;
vector<vector<int>> p(n);
set<int> st;
i64 SB = 0;
vector<int> fa(n);
iota(all(fa), 0);
function<int(int x)> find = [&](int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
};
for (int i = 0, j = 0; i < n; i++)
{
int s, a, b;
cin >> s >> a >> b;
s = (s + ans) % n;
S[i] = s, A[i] = a, B[i] = b;
if (i)
{
while (j && S[i] != S[j])
j = nx[j - 1];
if (S[i] == S[j])
j++;
nx[i] = j;
}
// 上一个状态等价于nx[i-1]-1
if (i && nx[i - 1] && S[i] == S[nx[i - 1]])
fa[i - 1] = find(nx[i - 1] - 1);
if (S[i] == S[0])
{
SB += B[i];
}
int p = i - 1;
while (~p)
{
// 找到等价点的父节点
if (S[p + 1] == S[i])
p = find(p);
// 不满足,p+1是长度,i-p-1
if (S[p + 1] != S[i])
{
SB -= B[i - p - 1];
}
p = nx[p]-1;
}
ans += SB * A[i];
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
while (T--)
{
solve();
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11796kb
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: 143ms
memory: 24068kb
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: 83ms
memory: 22032kb
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: 131ms
memory: 22836kb
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: 151ms
memory: 23796kb
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: 120ms
memory: 22460kb
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: 99ms
memory: 23988kb
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: 124ms
memory: 23756kb
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: 79ms
memory: 22720kb
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: 119ms
memory: 22016kb
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: 135ms
memory: 24060kb
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: 111ms
memory: 23692kb
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