QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#271691#7745. Trapping Rain WaterSatsuki#AC ✓984ms26944kbC++172.8kb2023-12-02 14:05:242023-12-02 14:05:25

Judging History

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

  • [2023-12-02 14:05:25]
  • 评测
  • 测评结果:AC
  • 用时:984ms
  • 内存:26944kb
  • [2023-12-02 14:05:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{int a,siz,sum;};
vector<node>ma,mb;
const int ni=2e6+10;
set<int>sa,sb;
int suma,sumb,sum;
int n,m,mx,ai[ni];
node ta[ni],tb[ni];
void solve(){
    suma=sum=sumb=0;
    ma.clear(),mb.clear();
    sa.clear(),sb.clear();
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    scanf("%lld",&ai[i]),sum+=ai[i];
    ma.push_back({0,0,0});
    mb.push_back({0,0,0});
    for(int i=1;i<=n;i++){
        int a=ma.back().a;
        if(a>ai[i]){
            ma.back().siz++;
            ma.back().sum=i;
            continue;
        }
        ma.push_back({ai[i],1,i});
    }
    for(int i=n;i>=1;i--){
        int a=mb.back().a;
        if(a>ai[i]){
            mb.back().siz++;
            mb.back().sum=n-i+1;
            continue;
        }
        mb.push_back({ai[i],1,n-i+1});
    }
    mx=ma.back().a;
    for(node i:ma){
        if(i.a==0)continue;
        sa.insert(i.sum);
        ta[i.sum]=i;
        suma+=i.a*i.siz;
    }
    sa.insert(2e6);ta[2000000].a=1e18;
    for(node i:mb){
        if(i.a==0)continue;
        sb.insert(i.sum);
        tb[i.sum]=i;
        sumb+=i.a*i.siz;
    }
    sb.insert(2e6);tb[2000000].a=1e18;
    scanf("%lld",&m);
    for(int j=1;j<=m;j++){
        int i,w;
        scanf("%lld%lld",&i,&w);
        int t=ai[i]+w;sum+=w;
        if(t>mx)mx=t;
        int siz=0;
        int q=*sa.lower_bound(i);
        if(ta[q].a<t){
            siz=q-i+1;
            if(ta[q].siz!=siz){
                sa.insert(i-1);
                ta[i-1]={ta[q].a,ta[q].siz-siz,i-1};
            }
                suma+=(t-ta[q].a)*siz;
                ta[q]={t,siz,q};
            while(ta[*sa.upper_bound(q)].a<=t){
                int p=*sa.upper_bound(q);
                suma+=(t-ta[p].a)*ta[p].siz;
                ta[p].a=ta[q].a;
                ta[p].siz=ta[p].siz+ta[q].siz;
                sa.erase(q);q=p;
            }
        }
        q=*sb.lower_bound(n-i+1);
        if(tb[q].a<t){
            siz=q-(n-i+1)+1;
            if(tb[q].siz!=siz){
                sb.insert((n-i+1)-1);
                tb[(n-i+1)-1]={tb[q].a,tb[q].siz-siz,(n-i+1)-1};
            }
                sumb+=(t-tb[q].a)*siz;
                tb[q]={t,siz,q};
            while(tb[*sb.upper_bound(q)].a<=t){
                int p=*sb.upper_bound(q);
                sumb+=(t-tb[p].a)*tb[p].siz;
                tb[p].a=tb[q].a;
                tb[p].siz=tb[p].siz+tb[q].siz;
                sb.erase(q);q=p;
            }
        }
        ai[i]=t;
        // printf("(%lld %lld %lld %lld %lld)\n",sumb,suma,sum,mx,n*mx);
        printf("%lld\n",sumb+suma-sum-n*mx);
    }
}
signed main(){
    int t;scanf("%lld",&t);
    for(int i=1;i<=t;i++)
    solve();return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7940kb

input:

2
6
1 2 3 4 5 6
2
1 2
3 3
5
100 10 1 10 100
1
3 100

output:

1
4
180

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 401ms
memory: 8048kb

input:

1000000
1
243315
1
1 211072
1
611907
1
1 931483
1
570785
1
1 223585
1
728162
1
1 547207
1
986415
1
1 479472
1
679456
1
1 889033
1
885718
1
1 118339
1
214466
1
1 464451
1
222854
1
1 70138
1
393099
1
1 909835
1
73671
1
1 100066
1
148162
1
1 110510
1
142367
1
1 58777
1
87989
1
1 684723
1
630453
1
1 719...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 lines

Test #3:

score: 0
Accepted
time: 367ms
memory: 7984kb

input:

500000
4
88702 934403 687350 528632
3
1 482595
4 331839
4 890431
1
80653
7
1 758092
1 691959
1 809872
1 96403
1 84281
1 713083
1 474452
1
664273
10
1 353641
1 827527
1 998495
1 749722
1 274869
1 974568
1 425227
1 59445
1 966182
1 558246
1
926871
9
1 791338
1 215107
1 534658
1 84624
1 331235
1 37824
...

output:

0
173121
247053
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
741826
865168
865168
865168
0
0
0
0
0
0
174868
174868
333931
333931
288889
288889
440773
1872642
1872642
2378495
2378495
2378495
461966
181899
929389
815797
587291
2126531
3019305
0
...

result:

ok 1000000 lines

Test #4:

score: 0
Accepted
time: 186ms
memory: 8000kb

input:

100000
9
272731 81240 712792 756370 371398 606967 695759 435539 424972
2
7 612034
3 447470
1
224913
5
1 899939
1 336327
1 645641
1 691033
1 575786
10
993768 216988 205093 811915 511384 502237 614274 381635 990027 42252
4
4 777608
7 652846
5 363199
10 770154
10
22666 635213 263573 639439 335341 44224...

output:

725866
1937542
0
0
0
0
0
3516033
3694466
3331267
3331267
1410899
1410899
2053173
295228
396517
396517
519182
102861
0
640249
0
166563
386556
386556
0
156838
458646
0
0
0
0
0
1371130
1015470
1876560
278983
956261
188367
128567
128567
1090711
1090711
1633568
847392
847392
1598365
1598365
1903522
19035...

result:

ok 551067 lines

Test #5:

score: 0
Accepted
time: 170ms
memory: 8000kb

input:

100000
70
145193 658934 178288 794526 30824 650903 967695 859363 412145 407205 567321 710188 164547 487440 13142 152385 446544 152988 944579 108224 666495 560673 346640 101467 19114 893706 417954 63192 581728 3542 325395 766608 850980 486235 954285 488688 946028 849470 34419 904827 91171 209915 3015...

output:

30677120
30128541
30854948
49823414
49638839
49025024
48817633
50489348
50351344
50122630
9235000
9221552
34754054
34235876
33805872
42534746
42534746
49619768
49410351
32190253
32167214
32933289
38505826
37536691
37224911
37110480
36766767
38508914
38253397
23476586
23398446
30165925
43254609
43178...

result:

ok 551150 lines

Test #6:

score: 0
Accepted
time: 260ms
memory: 7864kb

input:

100000
6
103019 33646 352613 101143 273682 996950
75
5 471413
3 227928
1 792208
3 579889
1 27745
5 360114
3 860851
3 481795
3 215974
6 905243
2 853741
2 988745
2 564176
5 540078
3 27307
2 735489
1 605101
3 356425
5 279706
4 954599
6 423370
1 55497
1 952552
6 211832
1 838067
4 720011
5 244544
4 37809...

output:

320843
548771
2120483
2009243
2036988
1893392
1893392
1893392
1893392
3487360
2633619
2598034
2598034
2057956
2057956
2057956
2057956
2057956
1823850
869251
1670391
1670391
1670391
2094055
2094055
1374044
1129500
1091691
1480407
1678799
1690719
1480407
621624
621624
621764
621764
621764
621764
62176...

result:

ok 1000000 lines

Test #7:

score: 0
Accepted
time: 220ms
memory: 12840kb

input:

12
30070
37311 92074 618927 991732 129711 612126 541583 552857 299118 773097 33928 750975 945843 707175 557221 117284 247929 241816 479602 219689 684863 410721 21888 219478 730953 691722 207141 430804 199900 788735 407544 718641 463430 105167 678681 969312 106835 841776 357671 170038 982105 139449 2...

output:

14975733644
14975532130
15304908882
15304596244
15304289202
15384458135
24369948725
24369178590
25146086589
31361231023
31360866614
33168588125
33913933403
33913190726
33912967806
33912394737
33911402760
33911251576
33910650481
33910032550
33909815157
33909044007
33908737999
33908519234
33907906607
...

result:

ok 1000000 lines

Test #8:

score: 0
Accepted
time: 227ms
memory: 18296kb

input:

15
13046
683844 914823 764255 815301 790234 184972 93547 388028 211665 554415 713159 183950 200951 842336 92460 150051 247500 501279 80836 443639 936708 509057 803822 417945 502793 974386 705915 125357 842615 537901 714164 455915 326431 768390 238289 697693 988548 603489 471107 299429 579552 669495 ...

output:

6511393333
6511367031
6511313514
6510937453
6511451573
6952181751
6951842212
6951700028
6951372679
6951127827
6950965928
7168060128
7564547382
7922588959
7922157467
7921473934
8849997946
8849727733
8849313772
8849154348
9654550314
9869468762
9869357105
9937069492
9936449944
13216847989
13215974949
1...

result:

ok 1000000 lines

Test #9:

score: 0
Accepted
time: 217ms
memory: 12484kb

input:

20
5440
588704 61481 472140 115810 658854 743034 305150 780684 361360 50516 554301 478790 543678 546138 279893 889899 960260 802881 66499 699500 254572 454419 833657 743179 661234 729965 591136 937826 626886 906880 664913 990362 385934 153747 840219 514676 746017 62847 187713 207556 37069 740466 517...

output:

2697137027
2696951543
2696836430
3183067067
3182712549
3182105664
3181535120
3248039037
3746000079
3806446616
3805934016
3805263366
3805193914
3824932137
3824424621
3824142748
4049870814
4049178363
4048258945
4048252277
4808405141
4807852833
4807242161
4806306714
4805660395
4851637232
4850954040
540...

result:

ok 1000000 lines

Test #10:

score: 0
Accepted
time: 224ms
memory: 12800kb

input:

10
100000
90732 246428 369649 684428 303821 287098 422756 301599 720377 177567 515216 750602 555733 321822 359420 742288 994857 429195 250193 371128 525280 742720 31645 375886 82443 783257 878866 747553 830750 389560 817287 461123 513394 259329 199478 361229 791746 726303 252157 235096 27694 291966 ...

output:

50039538061
50039191153
50106534477
50106230811
52196801975
57469678244
57469426372
57469398370
59892153908
72153685790
72153484158
74407840501
78819785708
78819017232
80495972221
80495835021
80495723309
94492459196
94491861541
94491853061
94491208232
100764527671
100764262902
106003695557
106003210...

result:

ok 1000000 lines

Test #11:

score: 0
Accepted
time: 230ms
memory: 18152kb

input:

10
100000
672280 26982 999126 809490 782598 250569 606744 235754 991855 438007 42256 359204 382166 292145 31529 990010 466607 859917 547137 434877 448866 850229 873324 722447 425355 844774 303727 429161 130621 908786 103366 579222 489530 61438 826782 228662 21820 313541 9563 451197 388912 490451 940...

output:

49911112270
49910931441
49910319479
49909691422
49908792798
49908350710
49909368043
52258869259
52258143521
78042780365
83557434088
85150641331
85150069017
85149258799
85148856364
85148525675
89950683245
109363804704
109363356748
109363006623
109362822557
109362693470
109362550531
110699179610
11069...

result:

ok 1000000 lines

Test #12:

score: 0
Accepted
time: 227ms
memory: 13016kb

input:

10
100000
221125 31727 661308 191447 485566 55256 823436 202614 328742 665743 602000 159294 951703 262468 479446 270437 714165 257935 587186 531329 596643 733546 747707 36304 511372 938995 985484 143474 397787 395308 580932 888810 432962 87739 197190 287584 251895 900778 542778 924193 7027 399336 47...

output:

49796976506
49796434172
49796199898
69770793240
95996031191
95996008038
95995137503
95995019834
95995013804
98955665964
106553759214
106552793428
106552363595
106551478931
106551402166
106551134885
106550538154
108924774251
108924475995
108923751520
108923285113
108923276401
108923063805
10892208664...

result:

ok 1000000 lines

Test #13:

score: 0
Accepted
time: 238ms
memory: 12132kb

input:

10
100000
90732 246428 369649 684428 303821 287098 422756 301599 720377 177567 515216 750602 555733 321822 359420 742288 994857 429195 250193 371128 525280 742720 31645 375886 82443 783257 878866 747553 830750 389560 817287 461123 513394 259329 199478 361229 791746 726303 252157 235096 27694 291966 ...

output:

50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
50039524687
...

result:

ok 1000000 lines

Test #14:

score: 0
Accepted
time: 243ms
memory: 16336kb

input:

10
100000
221125 31727 661308 191447 485566 55256 823436 202614 328742 665743 602000 159294 951703 262468 479446 270437 714165 257935 587186 531329 596643 733546 747707 36304 511372 938995 985484 143474 397787 395308 580932 888810 432962 87739 197190 287584 251895 900778 542778 924193 7027 399336 47...

output:

49795556552
49795556552
59432221566
59432221566
66302545985
88180582026
116693469153
141933950421
149307686070
149307686070
163837968260
200535778469
200535778469
200535778469
200535778469
220875580351
238422776683
238422776683
243163183022
286020262892
286020262892
292526956238
292526956238
3458894...

result:

ok 1000000 lines

Test #15:

score: 0
Accepted
time: 222ms
memory: 14396kb

input:

10
100000
1459 654597 228616 64902 923894 635457 89248 262691 502493 529230 358150 120075 123793 901567 170206 157661 980560 252956 29856 959273 298093 172317 325206 655282 807372 949939 30434 199219 838311 32511 644854 233366 983627 67417 190169 26366 335259 501578 288937 99903 659916 356178 768340...

output:

50009498022
50009221672
59139083152
62809001427
63527993385
67040410785
67814237971
67814140781
69210208531
69648664478
69648664478
107346979983
107346934701
107346549231
110942600460
111559474265
111558941720
111558847772
116177234043
128094436223
128093898646
128093820591
128093291673
134609532834...

result:

ok 1000000 lines

Test #16:

score: 0
Accepted
time: 243ms
memory: 12448kb

input:

10
100000
650541 217815 564977 630591 345182 758715 444983 424236 205803 327529 741114 256583 84894 905369 821416 682618 444904 834249 953746 758068 163357 431033 853038 615210 133877 368112 231447 910673 865037 446005 474379 965477 792996 9814 316716 49702 434590 864420 699200 826518 661509 97269 3...

output:

50152399706
50151785756
50151676430
50151676430
54264439080
54264236266
61123558668
65306166308
65305868968
65305485767
65304822178
65304822178
65304674964
65304416145
65304235505
65979393748
65979026171
76285455527
76284907163
78485141734
78485033034
79185852884
107737932258
107737363148
1077364149...

result:

ok 1000000 lines

Test #17:

score: 0
Accepted
time: 234ms
memory: 12492kb

input:

10
100000
992362 536810 973347 28053 761609 140383 748533 155415 908424 201328 494319 78947 19752 91475 400899 466162 405485 759523 213674 655008 820833 133342 444509 724782 809425 525286 941149 844672 613071 904449 767595 666397 271342 635481 297808 626546 225482 221693 118615 837455 315261 665182 ...

output:

49852457952
49852388910
49851896168
53464050474
56825556220
64490085279
68417974198
68417237950
75528903755
82919689027
82918850710
82918599819
82917646746
82916983037
82916598877
87699249610
87698557401
87698462765
87698076238
87697903632
89753437019
89973012416
89972381550
89971551389
89971169531
...

result:

ok 1000000 lines

Test #18:

score: 0
Accepted
time: 244ms
memory: 13228kb

input:

10
100000
624723 619970 578013 615422 109968 806875 742329 970234 516983 76965 831089 679711 823689 678069 816273 227674 420733 539186 769114 427821 250430 394200 467009 482415 976107 644150 392814 884936 288726 732016 731326 328119 369030 593469 738754 394252 757 323881 950718 436973 412177 93141 6...

output:

49904790217
49904776317
49904756320
52735735217
56585893679
56585059211
60910152954
60909847136
82698091563
82697995355
82748082104
82747177049
82747028080
82746698479
82746403264
84982614112
84982597562
84982151379
84981883998
84981403655
84980506848
84980295660
85587338755
85586551253
85585912199
...

result:

ok 1000000 lines

Test #19:

score: 0
Accepted
time: 483ms
memory: 13964kb

input:

10
100000
452712 307282 181875 1000000 657857 975332 325039 607940 465581 591409 1000000 184430 954211 670549 1000000 294458 968095 34513 1000000 859596 981214 591048 649717 111465 216420 674371 644616 219579 1000000 472685 1000000 152976 827559 390552 285095 484443 205758 303351 101040 49458 115345...

output:

45030436991
45030437051
45030437111
45030437201
45030437561
45030437611
45030438391
45030438601
45030441161
45030441881
45030445381
45030447251
45030447851
45030448371
45030450471
45030450471
45030450951
45030454011
45030457791
45030460451
45030461651
45030464381
45030467461
45030467691
45030469371
...

result:

ok 1000000 lines

Test #20:

score: 0
Accepted
time: 564ms
memory: 16424kb

input:

10
100000
45595 1000000 1000000 1000000 1000000 1000000 423633 808110 1000000 160087 379654 604962 174019 699390 1000000 288473 772646 276829 235910 1000000 379878 1000000 574288 913985 634775 1000000 793587 128724 651760 775301 1000000 293104 250512 918482 1000000 273870 676852 457264 703594 607023...

output:

35040502263
35040502263
35040502263
35040502263
35040502263
35040502363
35040502663
35040502943
35040503023
35040503293
35040503693
35040504023
35040504983
35040505243
35040505803
35040507003
35040507003
35040508023
35040508383
35040509333
35040509333
35040509753
35040510633
35040510863
35040511103
...

result:

ok 1000000 lines

Test #21:

score: 0
Accepted
time: 655ms
memory: 20064kb

input:

10
100000
771113 82916 265703 452960 68031 1000000 1000000 108850 330255 1000000 1000000 1000000 1000000 1000000 389195 252733 150548 917009 225030 992548 262296 228417 420155 882966 1000000 1000000 1000000 636844 659969 674742 349990 330930 359340 365237 1000000 1000000 431096 294152 440634 1000000...

output:

25109366025
25109366025
25109366065
25109366065
25109366065
25109366065
25109366065
25109366765
25109366765
25109366765
25109367465
25109367465
25109367825
25109367825
25109368105
25109368705
25109369025
25109369025
25109369025
25109369025
25109369025
25109369025
25109369025
25109369025
25109369025
...

result:

ok 1000000 lines

Test #22:

score: 0
Accepted
time: 982ms
memory: 26944kb

input:

10
100000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 lines

Test #23:

score: 0
Accepted
time: 473ms
memory: 16728kb

input:

10
100000
554836 841383 1000000 1000000 1000000 320897 506179 990779 979611 220042 177814 790422 661425 383210 1000000 902902 204871 143760 371953 1000000 617570 402028 466210 115913 194985 200243 269121 516422 108969 1000000 329596 803614 94226 176492 562598 216191 1000000 1000000 771189 731613 447...

output:

45270010979
45270011069
45270011089
45270011419
45270011579
45270011679
45270012099
45270012379
45270012379
45270012379
45270013379
45270013709
45270014909
45270014909
45270015469
45270015769
45270017849
45270017849
45270018389
45270021429
45270021429
45270022689
45270023349
45270024039
45270025959
...

result:

ok 1000000 lines

Test #24:

score: 0
Accepted
time: 550ms
memory: 21564kb

input:

10
100000
825804 854113 153575 943354 991725 664293 1000000 375855 777165 106442 39348 1000000 1000000 469083 1000000 402423 205599 1000000 1000000 1000000 323409 1000000 1000000 1000000 1000000 632331 91666 1000000 1000000 219398 434237 967255 970155 1000000 780606 133889 514248 138949 837352 10000...

output:

35174815978
35174816018
35174816018
35174816018
35174816058
35174816108
35174816348
35174816488
35174816568
35174816748
35174817148
35174817258
35174817618
35174817618
35174817898
35174818048
35174818048
35174818218
35174818218
35174818408
35174818408
35174819458
35174820778
35174820778
35174821258
...

result:

ok 1000000 lines

Test #25:

score: 0
Accepted
time: 629ms
memory: 22312kb

input:

10
100000
1000000 479700 1000000 134010 974150 550491 624791 217553 1000000 1000000 1000000 1000000 947647 1000000 554277 798733 232317 1000000 725984 1000000 181635 428023 1000000 17507 640407 50685 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 308536 117547 112187 1000000 1000000...

output:

25005302228
25005302268
25005302288
25005302288
25005302408
25005302458
25005302518
25005302658
25005302658
25005302838
25005302938
25005302938
25005302938
25005302938
25005302938
25005302938
25005303098
25005303098
25005303098
25005303858
25005305058
25005305058
25005305058
25005305748
25005305748
...

result:

ok 1000000 lines

Test #26:

score: 0
Accepted
time: 984ms
memory: 26684kb

input:

10
100000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 lines

Test #27:

score: 0
Accepted
time: 272ms
memory: 12304kb

input:

10
100000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202 407775 894325 963982 804784 968417 302156 631932 735902 895728 78537 723857 330739 286918 329211 539679 238506 63340 686568 361868 660016 287940 296263 224593 601449 836991 890310 823355 177068 11431 8580 291757 449218 37...

output:

50008336126
76059424883
99179062481
176052524981
199169062641
276042325145
299159362795
376033725277
399147862985
476025925393
499137763147
576014325585
599130763247
676009925633
699125063321
776005925673
799115563471
876002425703
899107763587
975998625739
999097263757
1075993225807
1099091363835
11...

result:

ok 1000000 lines

Test #28:

score: 0
Accepted
time: 413ms
memory: 23836kb

input:

10
100000
19 24 64 67 78 142 173 182 199 234 254 286 291 322 324 331 339 352 373 451 537 559 570 573 574 584 605 648 667 702 705 738 750 751 790 795 811 812 872 917 935 936 936 970 971 974 994 994 1015 1020 1025 1050 1058 1076 1106 1131 1140 1166 1167 1189 1190 1194 1212 1234 1255 1280 1306 1341 136...

output:

0
0
0
0
0
0
0
0
0
0
1
1
2
2
3
4
5
7
8
10
11
13
14
16
17
19
20
22
23
25
26
28
29
31
32
34
35
37
38
40
41
44
45
48
49
52
53
56
57
60
61
64
65
68
69
72
73
76
77
80
81
84
85
88
89
92
93
96
97
100
101
104
105
108
109
112
113
116
117
120
121
124
125
129
130
134
135
139
140
144
146
150
152
156
158
163
166
...

result:

ok 1000000 lines

Test #29:

score: 0
Accepted
time: 420ms
memory: 21700kb

input:

10
100000
15 33 39 45 52 83 120 128 136 159 163 166 175 193 220 236 254 259 264 274 302 321 342 355 360 365 366 420 432 477 478 522 544 571 578 579 606 612 617 655 660 663 680 691 696 711 756 815 845 847 855 924 929 933 984 993 1005 1009 1039 1045 1051 1077 1106 1178 1259 1301 1311 1428 1430 1445 14...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
2
6
6
10
10
21
21
30
32
35
40
43
45
52
54
62
72
92
100
112
118
126
132
136
138
146
154
162
166
174
176
184
186
202
212
232
240
260
268
278
288
313
321
331
335
345
351
376
386
401
409
434
440
445
449
459
474
499
511
528
542
548
566
596
611
618
648
676
706
720
750
773...

result:

ok 1000000 lines

Test #30:

score: 0
Accepted
time: 415ms
memory: 23636kb

input:

10
100000
9 17 23 31 74 98 160 202 219 222 225 232 234 236 251 270 303 314 424 435 437 450 452 454 500 519 535 559 568 578 671 690 739 770 771 817 829 830 898 904 1013 1018 1019 1019 1024 1029 1039 1044 1113 1129 1144 1154 1168 1175 1220 1246 1301 1388 1414 1422 1498 1527 1541 1550 1561 1591 1600 16...

output:

0
0
3
6
7
8
22
29
48
52
73
80
107
112
127
129
147
157
172
179
194
203
218
238
274
278
286
304
312
331
351
375
422
458
463
487
497
513
548
588
628
632
662
694
744
774
814
839
859
904
944
974
979
1014
1032
1042
1048
1094
1112
1118
1130
1184
1244
1268
1310
1328
1388
1394
1430
1460
1488
1549
1605
1612
1...

result:

ok 1000000 lines

Test #31:

score: 0
Accepted
time: 461ms
memory: 21596kb

input:

10
100000
29 154 167 178 187 210 247 257 269 270 273 273 325 348 358 378 417 431 455 487 489 495 498 502 511 512 515 582 596 599 678 708 710 722 723 734 753 791 807 845 855 861 888 891 915 936 958 971 1020 1037 1049 1064 1076 1091 1142 1195 1204 1217 1268 1268 1270 1287 1313 1314 1322 1328 1402 1408...

output:

0
0
0
6
6
19
19
33
33
79
79
91
91
115
115
163
163
187
187
231
231
239
239
263
282
346
377
385
425
501
541
571
630
715
790
852
945
1079
1121
1163
1226
1261
1350
1455
1477
1505
1571
1613
1668
1759
1781
1879
2077
2203
2357
2422
2648
2800
3002
3020
3188
3260
3462
3604
3694
3900
3975
4163
4283
4517
4697
...

result:

ok 1000000 lines

Test #32:

score: 0
Accepted
time: 454ms
memory: 19660kb

input:

10
100000
8 25 38 57 57 66 71 81 96 98 142 149 153 251 251 259 316 317 338 374 443 493 556 646 712 752 759 771 773 793 807 823 828 832 861 863 863 874 883 915 933 960 969 995 1000 1017 1025 1044 1058 1060 1067 1069 1083 1102 1113 1123 1153 1175 1194 1221 1242 1247 1269 1299 1330 1383 1439 1441 1481 ...

output:

13
41
87
117
224
293
618
626
927
931
1086
1145
1709
1712
1880
2015
2051
2251
2777
2783
2993
3155
3785
4265
5097
5448
5977
6341
6645
7277
7296
7552
8185
8799
9139
9253
9593
9973
10950
11703
12144
13026
13395
14356
14906
15667
16679
17651
18035
19161
19230
19568
20212
20712
21383
21906
22482
22544
227...

result:

ok 1000000 lines

Test #33:

score: 0
Accepted
time: 364ms
memory: 19696kb

input:

10
100000
2 19 24 93 102 105 143 158 244 270 272 370 395 396 399 414 416 433 454 475 487 505 533 536 536 579 602 623 655 663 665 672 682 691 694 697 714 718 735 741 744 764 766 768 773 777 792 812 814 823 849 858 866 928 992 999 1000 1017 1020 1036 1046 1092 1098 1106 1139 1173 1185 1235 1240 1246 1...

output:

13296360120
28824582114
40586762256
81188992192
106708781786
128604643860
128604643860
173415947616
173415947616
200158212760
200158212760
243636343180
243636343180
291443887010
291443887010
386655982730
386655982730
451061094602
451061094602
455670702408
455670702408
550317009444
550317009444
58482...

result:

ok 1000000 lines

Extra Test:

score: 0
Extra Test Passed