QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#747556 | #9372. Prefix of Suffixes | changziliang | AC ✓ | 166ms | 83624kb | C++14 | 1.8kb | 2024-11-14 17:31:26 | 2024-11-14 17:31:27 |
Judging History
answer
// 一个断点只会被找到1次
// 在boarder树上建出主席树
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
LL a[N], b[N];
int root[N], tot;
int n, S[N], dep[N];
int nxt[N];
struct SegmentTree {
int ls, rs, mx;
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define mx(x) t[x].mx
}t[N * 20];
int build() {
tot ++;
return tot;
}
void update(int p) {mx(p) = max(mx(ls(p)), mx(rs(p)));}
int ins(int p, int lp, int rp, int pos, int c) {
int tp = build(); t[tp] = t[p];
if(lp == rp) {
mx(tp) = max(mx(tp), c);
return tp;
}
int mid = (lp + rp >> 1);
if(pos <= mid) ls(tp) = ins(ls(tp), lp, mid, pos, c);
else rs(tp) = ins(rs(tp), mid + 1, rp, pos, c);
update(tp);
return tp;
}
int ask(int p, int lp, int rp, int l, int r) {
if(l > r) return 0;
if(l <= lp && r >= rp) return mx(p);
int mid = (lp + rp >> 1);
if(r <= mid) return ask(ls(p), lp, mid, l, r);
else if(l > mid) return ask(rs(p), mid + 1, rp, l, r);
else return max(ask(ls(p), lp, mid, l, r), ask(rs(p), mid + 1, rp, l, r));
}
int main() {
scanf("%d", &n);
LL lstans = 0; LL Sum = 0;
int j = 0;
for(int i = 1; i <= n; i ++ ) {
scanf("%d%lld%lld", &S[i], &a[i], &b[i]);
S[i] = (S[i] + lstans) % n;
if(i == 1) nxt[i] = 0;
else {
while(j && S[j + 1] != S[i]) j = nxt[j];
if(S[j + 1] == S[i]) j ++;
nxt[i] = j;
} // 考虑 i 接上 nxt[i]
root[i] = ins(root[nxt[i]], 0, n, S[nxt[i] + 1], nxt[i]);
if(S[i] == S[1]) Sum += b[i];
int now = i - 1;
int l = max(ask(root[now], 0, n, 0, S[i] - 1), ask(root[now], 0, n, S[i] + 1, n));
while(l > 0) {
Sum -= b[i - l];
now = l;
l = max(ask(root[now], 0, n, 0, S[i] - 1), ask(root[now], 0, n, S[i] + 1, n));
}
lstans += Sum * a[i];
printf("%lld\n", lstans);
}
return 0;
}
/*
3
0 1 2
1 2 3
2 3 4
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 12040kb
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: 0ms
memory: 12036kb
input:
100 14 14 932 64 528 396 32 293 948 27 757 520 31 620 590 41 157 353 17 858 394 20 927 729 36 722 94 44 567 360 82 123 320 22 935 893 2 142 6 45 668 346 33 625 617 15 550 105 48 691 923 75 569 300 57 768 381 31 288 541 63 829 37 12 395 25 5 959 974 57 31 635 15 880 113 79 310 959 84 618 516 69 951 9...
output:
13048 505144 778220 1483744 2061584 2207908 3007564 3871528 4544432 5072876 5187512 6058932 6191276 6813852 7396352 7908952 8552964 9083272 9799048 10067464 10840092 11208232 12102020 12130912 12951072 13239992 13815968 14702300 15007996 15761052 15934404 16122668 16309068 16858016 17299784 17661400...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 14188kb
input:
200 159 568 113 118 305 83 124 449 131 67 501 610 68 943 507 71 611 75 162 798 171 133 607 586 153 943 955 156 437 778 153 414 456 23 639 623 177 84 221 141 887 638 87 326 405 27 90 723 6 804 167 57 197 900 96 358 490 82 92 244 84 869 315 143 761 514 128 750 4 110 113 946 130 459 543 31 893 612 92 3...
output:
64184 98649 149386 205999 312558 381601 471775 540366 646925 696306 743088 815295 824787 925018 961856 972026 1062878 1085139 1125593 1135989 1234186 1320179 1404929 1417698 1469565 1570474 1611719 1665846 1733194 1770597 1848454 1893654 1909700 2007219 2073663 2112874 2136152 2138977 2211636 225875...
result:
ok 200 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 12056kb
input:
300 203 17 783 71 81 66 12 308 609 206 245 404 205 266 424 94 169 797 111 251 757 42 990 443 261 164 8 76 307 4 231 809 184 35 943 57 48 617 332 138 1 123 46 514 784 139 334 637 269 726 923 254 18 92 30 245 815 137 600 459 89 500 593 75 422 299 256 349 138 159 899 665 142 335 974 191 180 161 296 919...
output:
13311 76734 317898 509733 718011 850338 1046871 1822041 1950453 2190834 2824281 3562650 4045761 4046544 4449006 4710528 5278986 5293080 5484915 5954715 6346215 6676641 6949908 7653825 7916130 8057070 8776647 9013896 9458640 9657522 9889290 10589292 10805400 10831239 10999584 11239182 11850705 121505...
result:
ok 300 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 14124kb
input:
1000 893 197 325 231 902 183 40 481 495 265 152 704 789 458 546 257 30 366 746 546 332 815 523 683 770 152 647 966 785 793 61 915 864 666 972 536 677 183 290 163 533 374 931 943 508 626 226 823 643 596 767 619 563 613 52 340 813 163 591 752 989 342 326 156 97 25 196 373 732 223 693 539 825 835 642 9...
output:
64025 357175 513500 562900 711750 721500 898950 1068925 1118325 1373450 1670825 1986725 2046200 2219425 2525900 2599350 2793050 2976025 3086525 3278600 3389750 3421275 3542500 3767725 4039100 4290975 4600050 4680000 4977050 5243550 5328700 5568225 5749900 5906225 5986500 6140550 6425575 6597825 6750...
result:
ok 1000 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 17532kb
input:
10000 8580 58 19 2150 140 553 5919 883 170 317 527 945 5344 7 709 7959 659 507 7187 939 849 3335 426 64 4764 262 265 8161 985 298 9284 280 622 3651 897 691 4134 185 682 2483 107 233 8425 867 526 313 574 777 4927 363 617 9582 748 482 9102 701 339 950 875 300 8414 167 489 283 960 449 2835 919 42 4475 ...
output:
1102 3762 20539 30552 30685 43206 61047 69141 74119 92834 98154 115197 118712 120745 137218 148124 155021 169233 182552 199177 202350 220590 238051 250534 256766 265658 272365 287318 293531 310289 317224 330334 338428 352849 355186 364762 378328 385301 392236 399228 407474 422009 422978 440800 45107...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 12ms
memory: 18608kb
input:
30000 13880 717 630 1191 299 825 26934 951 753 27101 515 619 182 545 346 7268 103 397 14684 303 868 19398 140 289 13206 176 697 17902 630 839 1162 848 736 15955 356 137 24417 510 780 4520 181 846 3314 34 957 26097 106 902 13858 363 891 23031 645 55 3772 839 241 12366 89 726 19788 426 447 7206 130 69...
output:
451710 640080 1239210 1563660 1907010 1971900 2162790 2250990 2361870 2758770 3293010 3517290 3838590 3952620 3974040 4040820 4269510 4675860 5204430 5260500 5528880 5610780 5728590 6162030 6723990 7332570 7620480 7716870 8107470 8141490 8196300 8646750 8940960 9420390 9450000 9667980 10007550 10460...
result:
ok 30000 lines
Test #8:
score: 0
Accepted
time: 26ms
memory: 27256kb
input:
60000 15141 46 199 19010 441 493 17912 498 72 52140 490 319 22639 488 113 29542 861 631 42826 636 204 54035 119 129 43166 655 738 34809 796 266 51140 553 958 51372 546 362 16130 538 274 11967 36 914 6393 181 392 13421 64 790 5904 710 67 15300 629 166 55840 406 998 26995 519 66 30498 772 245 32790 67...
output:
9154 96913 196015 293525 390637 561976 688540 712221 842566 1000970 1111017 1219671 1326733 1333897 1369916 1382652 1523942 1649113 1729907 1833188 1986816 2121539 2159150 2207905 2244322 2348797 2513171 2646302 2757742 2930275 3006293 3175045 3220218 3413049 3582000 3683689 3811447 3932837 4078505 ...
result:
ok 60000 lines
Test #9:
score: 0
Accepted
time: 39ms
memory: 36136kb
input:
100000 41763 259 586 18012 415 257 49106 133 8 21008 815 804 63479 668 609 25833 967 333 87171 878 841 52931 676 498 37195 815 91 7676 715 764 76076 528 966 61688 836 66 33983 173 404 63347 432 931 95743 566 344 46797 588 984 24536 208 768 45169 165 81 82674 132 772 85254 678 526 33631 160 437 69689...
output:
151774 394964 472902 950492 1341940 1908602 2423110 2819246 3296836 3715826 4025234 4515130 4616508 4869660 5201336 5545904 5667792 5764482 5841834 6239142 6332902 6895462 7118728 7448060 7949676 8203414 8647016 9060146 9294546 9737562 10017670 10023530 10194642 10246796 10648206 11139860 11613934 1...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 108ms
memory: 58560kb
input:
200000 104981 915 978 72005 482 800 177948 444 819 60868 618 905 24176 877 566 90176 772 223 185967 142 556 180763 604 708 198471 724 841 34402 208 290 8187 897 955 88235 363 205 196825 836 315 97644 331 129 178234 937 695 84318 447 613 19259 154 29 131922 19 399 166202 191 667 124051 839 809 87123 ...
output:
894870 1366266 1800498 2404902 3262608 4017624 4156500 4747212 5455284 5658708 6535974 6890988 7708596 8032314 8948700 9385866 9536478 9555060 9741858 10562400 11465094 12236736 12573168 12763878 12901776 13215714 13596156 13952148 13954104 14520366 15281250 15641154 15815238 16357050 16569276 16765...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 135ms
memory: 69852kb
input:
250000 121542 607 158 231569 487 932 239941 651 529 45795 581 791 74176 655 970 91759 975 346 94309 839 207 11463 193 261 86873 925 19 44154 19 554 30042 763 99 88659 420 68 115717 893 99 241720 452 298 20794 955 560 57426 937 331 143339 797 775 60344 900 379 65644 192 326 180096 484 279 249207 16 8...
output:
95906 172852 275710 367508 470998 625048 757610 788104 934254 937256 1057810 1124170 1265264 1336680 1487570 1635616 1761542 1903742 1934078 2010550 2013078 2062690 2206470 2249130 2359730 2466380 2602576 2641602 2678732 2814770 2956812 3039762 3066780 3217828 3336486 3480582 3513288 3619306 3623888...
result:
ok 250000 lines
Test #12:
score: 0
Accepted
time: 166ms
memory: 80924kb
input:
300000 92392 788 667 125998 445 536 106789 562 630 143832 125 414 60682 87 818 230328 577 305 217466 702 568 165491 723 214 116644 442 488 28425 998 8 231786 562 161 47485 403 833 292372 99 930 99237 718 919 160725 12 853 121838 602 50 213981 589 802 242868 681 118 6625 249 562 295553 592 988 40616 ...
output:
525596 822411 1197265 1280640 1338669 1723528 2191762 2674003 2968817 3634483 4009337 4278138 4344171 4823077 4831081 5232615 5625478 6079705 6245788 6640652 7226278 7441719 7449056 7857260 8268799 8606301 8961145 9371350 9902282 10042352 10435882 10920791 11433047 11445720 11619807 11995995 1242154...
result:
ok 300000 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 11980kb
input:
10 7 518 71 0 121 862 6 607 138 3 513 337 8 873 337 6 647 917 5 417 1000 1 703 826 5 728 984 6 371 864
output:
36778 45369 88466 124889 481073 527010 556617 606530 658218 684559
result:
ok 10 lines
Test #14:
score: 0
Accepted
time: 163ms
memory: 83524kb
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 #15:
score: 0
Accepted
time: 146ms
memory: 83624kb
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 #16:
score: 0
Accepted
time: 153ms
memory: 83556kb
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 #17:
score: 0
Accepted
time: 154ms
memory: 83524kb
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 #18:
score: 0
Accepted
time: 157ms
memory: 83548kb
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 #19:
score: 0
Accepted
time: 135ms
memory: 81392kb
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 #20:
score: 0
Accepted
time: 150ms
memory: 83456kb
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 #21:
score: 0
Accepted
time: 137ms
memory: 83560kb
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 #22:
score: 0
Accepted
time: 141ms
memory: 83476kb
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 #23:
score: 0
Accepted
time: 140ms
memory: 81440kb
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 #24:
score: 0
Accepted
time: 140ms
memory: 81492kb
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
Test #25:
score: 0
Accepted
time: 135ms
memory: 83556kb
input:
300000 3 202 286 242229 250 355 170729 390 965 59188 23 350 52613 257 767 81989 937 90 114008 991 229 130582 123 781 95403 240 878 26764 122 875 291874 910 346 16753 960 516 42193 672 424 150002 908 158 46850 177 168 266492 757 160 228867 624 752 50404 378 29 242298 847 138 183167 897 45 226625 94 2...
output:
57772 129272 240812 247390 518011 785993 1069419 1104597 1173237 1208129 1783249 2057809 2250001 2653153 2733511 3071133 3249597 3357705 3716833 3973375 4000259 4229759 4374475 4440827 4446261 4464279 4470285 4690791 5206761 5875993 6001547 6281255 6438269 6652197 6844389 7030192 7732714 7993390 812...
result:
ok 300000 lines
Test #26:
score: 0
Accepted
time: 142ms
memory: 83552kb
input:
300000 1 550 720 204001 865 139 60966 233 900 251120 726 499 28400 155 712 216799 154 687 121 920 907 271242 857 335 254201 905 545 9376 809 24 166576 374 682 197295 127 647 23685 816 970 36167 605 919 200567 585 93 79365 860 906 60167 841 227 54646 85 276 269987 919 477 208306 595 991 90262 242 935...
output:
396000 1139035 1548882 2071602 2183202 2399880 4528760 5145800 6290625 7333426 7602706 7776315 8363835 8799435 9220635 9839835 10445355 10530015 11191695 12209740 12383980 13614564 13756404 13932342 14156982 14626422 15171462 15445827 16064307 16332723 16579107 16720947 16725987 17421507 17434143 17...
result:
ok 300000 lines
Test #27:
score: 0
Accepted
time: 134ms
memory: 83472kb
input:
300000 0 779 632 107672 620 661 206013 635 644 104692 548 207 244921 569 962 185313 531 904 149720 731 208 135681 667 583 14136 387 310 249582 961 767 107234 467 52 267319 97 215 155090 31 53 127191 334 575 144292 744 21 98500 774 516 93695 543 840 39115 780 775 125276 829 365 183938 672 880 67875 1...
output:
492328 1293988 1695308 2155080 2514688 2850280 3464320 3885864 4250418 5892767 6332681 6444910 6472810 6755708 7401500 8306306 8660885 9774725 10316062 11332126 11450310 11533316 12076850 12107342 12316534 12442934 13057870 13967950 14464490 15006870 15751446 15864458 16280482 16657279 17578927 1774...
result:
ok 300000 lines
Test #28:
score: 0
Accepted
time: 143ms
memory: 83448kb
input:
300000 3 992 840 66722 922 875 192240 98 715 109923 850 701 72 873 697 154779 419 884 102817 830 851 5619 339 714 20859 723 324 13540 246 504 282916 326 351 194648 400 407 158647 133 148 46930 503 199 124313 563 332 64477 477 141 196538 919 926 24580 336 31 31923 556 155 147646 527 601 4966 57 951 2...
output:
833280 1607760 1690080 2999930 4345223 4697183 5394383 5679143 6286463 6617087 7005353 7341353 7453073 7975690 8635526 9103463 9875423 10168079 10652355 11095035 11142915 11532705 12187065 12376905 12943065 13377065 14234215 14586840 15347600 15761285 15821521 16581721 17344021 17365662 17585182 177...
result:
ok 300000 lines
Test #29:
score: 0
Accepted
time: 0ms
memory: 14076kb
input:
28 1 522 575 10 426 445 5 772 81 9 447 629 8 497 202 9 775 325 22 982 784 21 417 156 22 932 902 2 728 537 1 857 739 1 918 211 8 679 506 23 340 568 11 868 16 11 940 263 14 593 449 24 991 310 0 355 68 18 431 580 2 757 218 9 934 328 14 676 355 23 221 80 11 922 545 5 511 67 13 467 674 26 691 504
output:
300150 545100 1051532 1589720 2188108 3373083 5325299 6154295 8847775 10685975 12849900 15361548 15895242 16355602 17051738 17839458 18336392 18906217 19134482 19411615 20063392 20970306 21626702 21858973 22462883 22756708 23339991 24085580
result:
ok 28 lines
Test #30:
score: 0
Accepted
time: 153ms
memory: 81504kb
input:
300000 222211 801 726 240685 475 450 282085 475 730 276735 530 374 268335 982 26 103843 876 319 204343 742 791 69671 942 238 227603 714 862 3179 392 586 103195 517 878 11535 809 869 170694 806 771 28974 529 325 26069 632 327 198165 758 229 54407 395 180 225412 847 209 195582 921 578 175554 108 182 3...
output:
581526 1140126 2045476 3253876 5518368 7817868 10352540 13794608 17019032 19019016 22110676 27651517 33793237 37996142 43224046 49667804 53096799 60626629 69346657 70388857 76724603 77531419 88838563 94494703 97503643 106662727 109460667 114570342 122531743 133975897 139390783 145676824 158983024 16...
result:
ok 300000 lines
Test #31:
score: 0
Accepted
time: 110ms
memory: 83448kb
input:
300000 38339 691 618 298983 484 549 212189 819 420 49749 621 869 217469 477 570 138135 905 730 95213 985 313 90710 776 203 12332 110 246 161644 182 510 279568 523 717 58918 665 299 153376 986 498 206406 62 950 209040 39 564 142828 700 257 292946 469 173 248817 959 247 111014 257 851 121406 607 627 1...
output:
427038 726150 1576272 2220870 2987886 4443126 6335311 7826007 8064377 8458771 9967103 11884963 15219615 15429299 15583193 18345393 20277204 24227325 25504615 28521405 29456297 30137201 33249353 33657313 39177061 44402593 46177937 48033317 53466293 53739503 58885042 61309464 70548360 75993372 8422141...
result:
ok 300000 lines
Test #32:
score: 0
Accepted
time: 125ms
memory: 83464kb
input:
300000 21763 860 867 229246 798 256 186663 305 937 119842 765 21 93625 922 286 224172 604 915 185434 719 878 168783 253 57 71268 566 358 169326 552 109 87429 312 866 151712 319 718 51201 425 357 55704 99 64 184019 995 284 260793 117 35 48657 827 883 23131 94 485 7647 187 534 136963 583 435 53263 375...
output:
745620 1437486 1701921 2381241 3199977 3736329 5006083 5452881 6452437 7487437 8072437 8670562 9619162 9840130 12060970 12326209 14201018 14414116 14937903 16570886 17621261 18913594 19323626 20315757 23238757 25762807 27449457 31462872 32747932 32901372 33606090 39171125 42252868 42710248 47848348 ...
result:
ok 300000 lines
Test #33:
score: 0
Accepted
time: 143ms
memory: 83528kb
input:
300000 5187 403 549 269759 292 257 55851 136 522 251014 586 790 127254 949 131 267753 751 556 3473 37 726 248140 489 91 113574 553 836 61045 554 844 67581 782 92 51896 674 825 128066 428 925 169137 291 61 5206 600 703 10433 292 440 95615 170 235 126514 896 836 75218 640 30 132405 644 283 107015 946 ...
output:
221247 381555 456219 777933 1423253 1933933 1959093 2291613 3129961 3969825 5155337 6177121 7221869 7932200 9396800 10109572 10564492 12962188 14674828 16398172 19288202 21866622 22465402 25049932 27251092 29844012 31673332 31829372 32993358 33462302 35706534 38273165 40047098 44230996 47942839 5269...
result:
ok 300000 lines
Test #34:
score: 0
Accepted
time: 108ms
memory: 81440kb
input:
300000 121315 801 259 108200 738 549 43551 689 944 59659 644 764 215443 226 591 218933 81 791 28227 351 519 86170 372 209 190129 374 619 120009 925 701 110783 553 434 84475 177 334 248300 566 888 202915 360 984 291255 560 107 122239 301 676 266423 475 110 266916 682 856 188355 91 257 14375 281 653 6...
output:
207459 398601 577052 743848 802382 887432 1255982 1646582 2039282 3010532 3831184 4093852 4933796 5468036 6299076 6949236 7975236 9448356 9644916 10251876 10645638 10690898 11915181 13881728 13954144 15900979 17301334 18801877 18858802 20379838 22518125 24257545 24533453 25433153 27532453 27606397 3...
result:
ok 300000 lines
Test #35:
score: 0
Accepted
time: 132ms
memory: 83488kb
input:
300000 104739 411 888 32239 933 403 29234 840 879 126796 122 700 60817 75 930 239107 60 287 37131 379 893 254600 431 750 12488 56 849 156234 270 419 17721 998 398 285173 745 205 9632 895 52 161565 490 922 88894 950 49 91026 351 328 90000 324 734 40998 844 618 145250 534 858 200724 126 265 87157 245 ...
output:
364968 1193472 1939392 2047728 2114328 2167608 2842607 3610218 3709954 4190824 5968262 7295107 8935642 9833812 11575162 12218545 12812437 14359489 15796483 16135549 16794844 17376100 19714579 21140809 23922679 25307500 28260562 29654554 29746264 32039014 34868310 36931946 36961114 39214342 42364486 ...
result:
ok 300000 lines
Test #36:
score: 0
Accepted
time: 141ms
memory: 83468kb
input:
300000 220867 381 331 87236 73 55 177177 331 803 192727 531 1 289498 366 964 42766 576 160 101223 387 360 245372 79 881 142104 403 294 67772 987 299 196639 819 950 76543 412 523 51613 429 120 80778 124 633 202736 894 317 28290 123 441 254327 566 420 114024 892 683 222688 491 167 246363 373 724 22515...
output:
126111 150274 259835 435596 556742 747398 875495 971243 1459679 2655923 3648551 4147895 4667843 4818131 6185057 6373124 7238538 8602406 9353145 9923462 10189508 11373824 12521360 12590016 14487864 14728160 14926772 16846688 18554438 20251838 23249888 23387888 23425838 25933988 26316938 27038074 2793...
result:
ok 300000 lines
Test #37:
score: 0
Accepted
time: 126ms
memory: 83548kb
input:
300000 71587 508 2 161176 526 919 38641 427 301 79118 656 807 245922 988 928 172074 394 532 37799 239 11 167293 238 442 63635 808 179 7992 152 14 158997 591 737 93357 964 484 86989 862 448 159095 134 394 1354 703 259 4083 912 810 35829 452 45 24282 936 372 291263 29 79 26040 103 993 170878 454 613 2...
output:
1016 2068 2922 4234 6210 6998 7476 7952 154200 181712 288683 463167 619189 643443 770686 935758 1037910 1249446 1256000 1279278 1381882 1487424 1606074 1793428 2340988 2628808 3165838 3554863 3691168 3729193 3791203 4098913 4398704 4960490 4981106 5649408 6007611 6640694 6713709 7553811 7835197 8967...
result:
ok 300000 lines
Test #38:
score: 0
Accepted
time: 123ms
memory: 83424kb
input:
300000 12450 233 666 72425 725 627 220045 260 812 159932 42 402 31668 393 804 131890 577 734 260702 803 537 246940 97 361 65345 897 752 217599 289 353 115585 45 928 108024 848 936 164681 320 5 282511 518 820 165722 204 360 38622 888 935 178006 993 117 314 575 103 200200 792 915 14423 209 199 129261 ...
output:
155178 638028 811188 839160 1100898 1485180 2019978 2084580 2681982 2874456 2904426 4262922 4775562 5605398 5932206 7354782 8945568 9866718 11135502 11470320 12692646 13024260 13829835 15289185 15440985 15879135 15917085 16686435 17228085 17348835 18894435 20031210 20610810 22379594 23521858 2377791...
result:
ok 300000 lines
Test #39:
score: 0
Accepted
time: 118ms
memory: 83556kb
input:
300000 10679 981 367 51947 246 321 166904 172 456 173512 770 39 238887 698 336 112777 291 382 141926 33 757 258908 978 391 110289 231 216 258698 799 885 19822 323 801 67136 486 296 166753 588 985 14881 53 206 189340 106 38 75579 640 501 56014 595 699 261570 389 723 287968 152 485 231270 248 502 2317...
output:
360027 450309 513433 796023 1052189 1158986 1171097 1530023 1614800 1908033 2026574 2204936 2420732 2440183 2479085 2713965 2932330 3075093 3130877 3221893 3308872 3555496 3618620 3656788 4013145 4259402 4529881 4541992 4837427 4859080 5199289 5547201 5846757 5880041 6045833 6371765 6931941 7488349 ...
result:
ok 300000 lines
Test #40:
score: 0
Accepted
time: 122ms
memory: 83524kb
input:
300000 231321 27 524 187525 615 748 276658 99 84 25663 420 608 271467 150 396 296640 333 545 269103 462 950 242397 687 65 187617 988 702 250857 860 472 267184 12 855 15609 667 761 93021 662 76 156765 853 906 1618 255 638 37934 914 904 55358 526 868 32872 946 312 30679 87 615 16305 269 655 8203 115 1...
output:
14148 336408 388284 608364 686964 861456 1103544 1463532 1981244 2431884 2438172 2787680 3134568 3581540 3715160 4194096 4469720 4965424 5011012 5151968 5212228 5226900 5494140 5672824 5949496 6000848 6410092 6671568 7105964 7352768 7757296 8083748 8345224 8791672 8811060 9052100 9120744 9318292 941...
result:
ok 300000 lines
Test #41:
score: 0
Accepted
time: 118ms
memory: 83468kb
input:
300000 147013 763 337 155488 240 237 222536 141 715 269332 509 64 143158 920 554 137528 97 430 182916 652 924 261263 587 461 39013 601 92 113739 54 475 241623 749 496 182878 667 656 192054 873 667 48166 157 905 133544 332 692 179293 307 791 95832 214 398 2792 905 230 266972 286 398 176861 487 38 220...
output:
257131 338011 385528 557061 867101 899790 1119514 1317333 1519870 1538068 1790481 2015260 2309461 2362370 2474254 2577713 2649831 2954816 3051198 3215317 3243962 3518954 3648699 3750136 4047707 4225643 4430876 4482437 4780682 4855159 4899306 4907731 5120378 5285845 5317186 5560500 5805499 5948724 60...
result:
ok 300000 lines
Extra Test:
score: 0
Extra Test Passed