QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734363#8590. Problem SetterZhaoZiLong100 ✓182ms6836kbC++14665b2024-11-11 09:24:222024-11-11 09:24:22

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 18
Accepted

Test #1:

score: 18
Accepted
time: 1ms
memory: 5684kb

input:

1000 1
570339 324084
75781 292531
427864 843267
928484 613828
883296 385343
733451 782070
756314 89477
786410 133722
455015 841750
146307 536680
992681 107898
657731 633895
764691 258779
142935 640379
445046 717170
227758 578083
526095 660806
859673 757597
898726 4088
719881 887973
850810 674331
752...

output:

575102

result:

ok single line: '575102'

Test #2:

score: 18
Accepted
time: 1ms
memory: 5688kb

input:

1000 1
93555 337906
136252 661901
127242 762569
370437 288257
767189 41343
788899 716075
654667 69573
991915 927883
7763 509983
986424 963695
362599 476740
955459 125250
620759 316409
611815 579388
450941 792473
270525 969538
184881 646954
624056 237034
592281 938786
454775 905658
805770 146630
6691...

output:

266314

result:

ok single line: '266314'

Test #3:

score: 18
Accepted
time: 1ms
memory: 3724kb

input:

1000 1
372915 410729
261932 931394
243312 331965
724590 783322
487345 73014
917626 421202
52572 541824
13651 326164
162767 857461
39807 712157
363164 412246
748463 240053
627875 449914
356280 426806
472871 238292
317364 708065
530316 302867
985730 776991
389066 595962
383264 231238
755140 612569
900...

output:

18699

result:

ok single line: '18699'

Test #4:

score: 18
Accepted
time: 1ms
memory: 5680kb

input:

1000 1
973869 701086
558011 774964
697322 753066
791372 665308
8732 871957
842731 544161
846847 511267
48968 129792
601946 266150
80870 311886
436651 574009
696653 679800
550300 95648
733297 433189
20014 746152
691080 377304
797922 412118
753742 696618
374002 692110
676184 965244
896440 485847
25751...

output:

225812

result:

ok single line: '225812'

Test #5:

score: 18
Accepted
time: 1ms
memory: 3732kb

input:

1000 1
446735 220359
691517 839587
111030 978505
365818 886684
984994 25626
759094 161155
535967 370952
202441 528116
458607 347342
321712 893280
511738 62329
945252 466145
434938 569254
923698 152927
434132 616641
158841 717741
35249 127470
952799 690934
451125 357306
320955 931834
709677 396258
42...

output:

907138

result:

ok single line: '907138'

Test #6:

score: 18
Accepted
time: 1ms
memory: 5628kb

input:

1000 1
601061 798635
853232 805018
903746 742357
851779 891012
871518 591965
787106 438276
800008 833789
97461 455880
918209 71464
738824 721438
142105 117316
651442 950621
469940 155734
390371 819443
864285 858331
667676 294253
995541 511904
673777 634772
669846 669616
85323 280317
517325 300991
79...

output:

759810

result:

ok single line: '759810'

Test #7:

score: 18
Accepted
time: 1ms
memory: 5628kb

input:

1000 1
475214 435913
79469 670572
187835 156303
287622 752976
668304 570286
851398 338524
637600 938147
883397 950768
17064 623512
444573 908727
365435 776654
889223 984546
804670 743408
169630 395052
347470 433540
105900 181524
678796 566786
953677 639129
29480 630407
43286 936697
320068 162363
552...

output:

719341

result:

ok single line: '719341'

Test #8:

score: 18
Accepted
time: 1ms
memory: 5772kb

input:

1000 1
934730 460637
249010 431133
278189 613881
957564 521984
736935 332621
703360 564511
118172 714420
947838 878574
178322 44348
11458 606815
34008 385140
13323 140563
679510 670674
82238 970202
244493 99898
960974 433944
531664 48342
586720 74325
527854 988420
560251 926189
992269 510883
858041 ...

output:

462952

result:

ok single line: '462952'

Test #9:

score: 18
Accepted
time: 1ms
memory: 5704kb

input:

1000 1
38704 346504
483075 126353
822919 268051
576702 147796
753513 132648
592287 492765
172980 356260
865509 450281
978835 204094
829982 450140
332545 150541
744383 403569
705398 73425
307433 347343
119867 23193
820121 126158
69812 51140
704003 291934
167826 477177
271495 349467
658879 329028
5147...

output:

0

result:

ok single line: '0'

Test #10:

score: 18
Accepted
time: 1ms
memory: 3720kb

input:

1000 1
885301 271328
384259 13091
411940 185829
915824 306781
143642 88748
85829 245942
919389 73320
501732 402705
35599 44992
771955 383893
47482 449389
803506 311468
855254 280722
158647 224849
896120 201358
987243 268364
657053 147875
855508 280614
718336 89658
123939 2017
218272 414547
715521 20...

output:

0

result:

ok single line: '0'

Test #11:

score: 18
Accepted
time: 0ms
memory: 3572kb

input:

5 1
3 4
1 2
5 6
2 8
4 0
3 6

output:

2

result:

ok single line: '2'

Subtask #2:

score: 16
Accepted

Dependency #1:

100%
Accepted

Test #12:

score: 16
Accepted
time: 0ms
memory: 3660kb

input:

1000 1000
389868 910117
138872 863197
945257 314232
767951 66789
16890 292700
183331 674706
406355 902607
544759 783299
202033 367674
144750 418158
965750 393368
848676 358716
67427 711157
128330 967985
223199 421907
386765 736937
238840 373101
229494 95780
28597 7848
65650 153531
388679 260846
3364...

output:

481417626

result:

ok single line: '481417626'

Test #13:

score: 16
Accepted
time: 1ms
memory: 3660kb

input:

1000 1000
614275 96168
531562 262620
851059 259823
270996 4606
726571 668025
257152 540510
183186 131226
911124 940546
959363 767223
605136 291723
79490 343201
27194 46893
806137 829559
180286 255563
147362 534706
369128 82339
20561 496718
987911 550372
54995 920737
283682 449291
927525 548290
82621...

output:

493298570

result:

ok single line: '493298570'

Test #14:

score: 16
Accepted
time: 1ms
memory: 5760kb

input:

1000 1000
558510 304225
989461 562167
173551 781511
686241 762375
308828 456702
367253 65755
534253 926000
19036 627917
430629 920015
316473 486736
748511 859701
737304 395517
806891 985467
619510 526919
87559 93389
317881 700818
563616 252417
231934 29167
147624 518420
583626 163943
460781 792373
5...

output:

492343959

result:

ok single line: '492343959'

Test #15:

score: 16
Accepted
time: 1ms
memory: 5704kb

input:

1000 1000
13422 973726
352293 682037
339992 346145
335584 427188
238298 991025
228025 918111
565299 504369
442455 785890
851931 15592
963631 193232
899774 362347
407730 792236
348439 555650
192084 686132
440910 667855
646484 648130
237914 472473
865418 938120
454361 512640
443257 137710
975176 56128...

output:

497625644

result:

ok single line: '497625644'

Test #16:

score: 16
Accepted
time: 1ms
memory: 5640kb

input:

1000 1000
820658 23384
663852 909131
159528 995497
594821 606325
6065 173518
605139 281390
856403 499554
441941 717989
433216 427008
715225 802378
990166 330521
706451 274317
536957 944519
708735 850717
922370 203004
586605 181909
38148 955093
804625 694776
635007 882426
125630 766871
781480 850204
...

output:

490386884

result:

ok single line: '490386884'

Test #17:

score: 16
Accepted
time: 1ms
memory: 5680kb

input:

1000 1000
676858 699209
194784 904616
196351 860321
104875 911726
793059 496178
614525 416312
35920 285598
497822 971841
171395 30441
827290 151769
289671 966501
329746 955616
491598 554086
832482 940485
308474 482191
960353 638372
196059 514679
481952 613767
186571 172925
298453 467427
173698 57008...

output:

496586380

result:

ok single line: '496586380'

Test #18:

score: 16
Accepted
time: 1ms
memory: 5640kb

input:

1000 1000
215203 434035
753242 763225
723864 226558
638810 962395
378633 231506
585507 247674
825989 712478
369934 792816
586514 313805
153992 748610
219140 206830
484632 260361
708285 239529
268815 902348
672930 207262
337489 479591
114616 707031
681886 556278
804366 111222
664871 476564
597327 283...

output:

485524252

result:

ok single line: '485524252'

Test #19:

score: 16
Accepted
time: 1ms
memory: 5708kb

input:

1000 1000
9086 26829
100151 723256
257731 219730
992857 651480
238768 985667
898220 256944
870861 587252
354386 254396
471711 175863
269314 437451
14700 294484
770537 75116
962372 44373
506988 885345
637295 500598
703291 888354
493393 918855
55080 716132
369950 99141
145439 128628
262594 10622
65898...

output:

498937929

result:

ok single line: '498937929'

Test #20:

score: 16
Accepted
time: 2ms
memory: 5696kb

input:

1000 1000
740254 245104
703434 376995
971200 279010
673088 503829
155130 842310
805520 37857
841831 289884
358234 112413
513803 155256
745106 904223
981692 49943
344018 14404
944899 107602
352258 793526
393938 612654
501350 331482
266158 206960
129396 113002
342765 157140
302822 741090
587774 168609...

output:

498811741

result:

ok single line: '498811741'

Test #21:

score: 16
Accepted
time: 1ms
memory: 3736kb

input:

1000 1000
935426 843538
143760 137957
412448 423006
962529 795818
798792 384807
192162 367379
109172 446330
901151 707556
715878 488171
326019 199644
888497 308614
656789 150739
575079 26513
253286 633080
390373 685393
910927 286394
165545 721316
509437 357578
115492 404339
133582 46629
204862 88359...

output:

517123168

result:

ok single line: '517123168'

Test #22:

score: 16
Accepted
time: 1ms
memory: 5620kb

input:

3 3
2 5
1 1
8 3
3 2
9 4
1 3

output:

4

result:

ok single line: '4'

Test #23:

score: 16
Accepted
time: 0ms
memory: 3728kb

input:

3 4
2 3
1 1
8 4
2 0
7 0
1 0
8 0

output:

11

result:

ok single line: '11'

Subtask #3:

score: 26
Accepted

Test #24:

score: 26
Accepted
time: 161ms
memory: 6708kb

input:

200000 200000
443848 257048
353855 430518
112240 460358
489050 850745
18217 643349
796031 335731
553602 81823
556808 39341
963397 797473
713023 273372
888193 500234
801660 980841
416233 163140
649254 659678
434013 461662
805451 259446
107168 839690
438518 100393
584335 435627
735040 11809
906814 672...

output:

199985649927

result:

ok single line: '199985649927'

Test #25:

score: 26
Accepted
time: 161ms
memory: 6832kb

input:

200000 200000
333130 577648
41080 822997
187466 358241
16874 51949
553684 775680
888225 58652
283594 632965
971667 522676
73986 76332
905359 631172
633389 994061
934283 902840
110896 341628
432967 332824
239445 649641
689728 484799
124192 63092
153968 530823
906578 363019
287528 659642
141227 738119...

output:

199982798008

result:

ok single line: '199982798008'

Test #26:

score: 26
Accepted
time: 162ms
memory: 6824kb

input:

200000 200000
611734 279091
714031 285014
27470 340840
153223 730480
928132 593181
347393 404865
272959 638606
963277 818505
269192 633347
90450 816938
355398 27411
731512 872519
490897 450482
160071 49026
246985 835302
147838 296619
230153 623742
138143 771274
65730 553610
625075 37550
630552 39770...

output:

199983714403

result:

ok single line: '199983714403'

Test #27:

score: 26
Accepted
time: 157ms
memory: 6828kb

input:

200000 200000
730837 46140
409083 509621
325651 932449
863659 658681
757387 809828
264223 76652
183168 539497
509871 264882
932759 497239
432560 969985
175115 36367
282045 503058
914403 6069
352721 594493
481605 484947
379039 160881
102071 906584
728660 618381
667626 563020
930844 363389
766516 9447...

output:

199987103986

result:

ok single line: '199987103986'

Test #28:

score: 26
Accepted
time: 160ms
memory: 6704kb

input:

200000 200000
202263 268030
52175 729770
426294 608774
109305 63522
351625 711645
622711 334732
426748 820206
632533 560753
792623 713969
842108 25680
971646 622533
497870 219646
22559 492708
526446 145330
881333 95276
221073 611609
62925 526673
624216 350190
181800 873313
947674 307624
231389 48826...

output:

199987840885

result:

ok single line: '199987840885'

Test #29:

score: 26
Accepted
time: 160ms
memory: 6788kb

input:

200000 200000
723340 41402
840645 717625
669541 388205
755135 669311
963721 828311
538102 363770
484744 891772
737592 103694
809381 122715
575127 784624
977291 839505
112953 134765
933841 162362
381951 621353
148706 561324
533734 59704
381455 223728
258576 207336
29208 141318
603634 286254
244493 54...

output:

199985653996

result:

ok single line: '199985653996'

Test #30:

score: 26
Accepted
time: 149ms
memory: 6828kb

input:

200000 200000
670051 306615
577156 738705
640566 327037
936176 603057
377798 629461
44518 941417
876796 417153
492716 458444
986122 810302
412582 446900
959063 522002
354960 172247
492090 726069
106849 65061
618188 876374
420913 19582
899919 146348
161662 912188
713528 710206
969970 994962
661873 63...

output:

199990956643

result:

ok single line: '199990956643'

Test #31:

score: 26
Accepted
time: 162ms
memory: 6640kb

input:

200000 200000
421634 601120
410450 522375
143766 763196
728302 935843
172686 793444
822230 957006
189007 876154
803510 38425
667537 878764
332374 1089
2229 254789
387954 758908
206210 773509
334292 338719
277064 692407
80497 143585
110340 865160
708089 186694
841274 60229
305213 651600
613528 654675...

output:

199990875965

result:

ok single line: '199990875965'

Test #32:

score: 26
Accepted
time: 156ms
memory: 6828kb

input:

200000 200000
524169 350466
154101 375584
300748 321070
55639 671269
806555 754278
115597 483518
761276 677287
690370 393218
471252 262379
356602 458614
22209 490102
86239 393933
530300 751999
542125 691747
138733 469124
351600 743057
409699 884219
485557 382905
880614 748819
425515 964318
894775 22...

output:

199988650170

result:

ok single line: '199988650170'

Test #33:

score: 26
Accepted
time: 163ms
memory: 6748kb

input:

200000 200000
346532 83446
963647 129601
948421 492041
368489 226646
387685 53098
520613 707840
907096 156254
356463 314449
989590 400608
594784 275269
671467 366763
316115 727090
79435 730997
63228 991553
16437 617043
700774 614918
543703 573042
822631 527951
986185 10523
664730 584245
95750 758299...

output:

199995955822

result:

ok single line: '199995955822'

Subtask #4:

score: 40
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #34:

score: 40
Accepted
time: 182ms
memory: 6704kb

input:

200000 200000
767321 683727
414753 236037
345706 834005
158059 821181
272678 463929
374092 641675
177274 969513
704311 178222
548635 522489
842714 536216
783335 777285
450821 699755
998737 315757
865715 508153
261693 53137
904709 620297
992436 779665
423427 539096
488767 527692
145454 50039
383394 4...

output:

99935155746

result:

ok single line: '99935155746'

Test #35:

score: 40
Accepted
time: 181ms
memory: 6796kb

input:

200000 200000
74003 377248
671314 302317
306139 440793
134461 77794
314980 902368
554840 894540
736960 880349
981460 997741
979249 13524
221906 257559
347294 378075
632420 317298
988415 17029
98340 97015
643854 744576
814351 79623
311416 392213
665014 375947
999822 923809
598487 624752
500639 820677...

output:

100053766581

result:

ok single line: '100053766581'

Test #36:

score: 40
Accepted
time: 177ms
memory: 6740kb

input:

200000 200000
272622 854399
718967 587289
116162 978061
671891 288341
586495 129690
590690 134703
993665 395532
298726 337287
8356 702945
286150 346358
427906 981876
214422 170564
827764 293795
777716 103193
383588 415935
641613 569684
249023 459850
859420 693368
758822 476503
753025 969551
314034 7...

output:

99868867617

result:

ok single line: '99868867617'

Test #37:

score: 40
Accepted
time: 182ms
memory: 6756kb

input:

200000 200000
800778 114835
629071 937368
894856 30580
66430 174304
170256 449844
893587 627458
505172 394925
729018 355123
432861 8059
102013 527157
300612 545368
889076 422843
630516 802329
369926 93507
685550 730242
382172 627288
721532 472960
152403 339813
427242 116504
21712 920963
405381 65761...

output:

99823215051

result:

ok single line: '99823215051'

Test #38:

score: 40
Accepted
time: 182ms
memory: 6820kb

input:

200000 200000
974079 434274
641382 224569
127239 696196
447853 842534
664280 145667
270447 742655
664914 35839
974856 939399
571988 67101
131830 992405
766283 637843
22005 372568
695313 312055
163727 30598
41230 452750
163802 994966
880005 230518
967994 972779
162577 367304
521680 254268
454826 6138...

output:

100110373173

result:

ok single line: '100110373173'

Test #39:

score: 40
Accepted
time: 182ms
memory: 6836kb

input:

200000 200000
122346 379877
687388 205478
650907 502602
43092 637027
102847 981656
130214 628810
713070 429928
203091 808427
905008 244162
522803 197898
440381 435806
554194 521508
525548 116478
639308 892189
226871 919295
304378 323011
395468 27359
522389 805764
379827 649814
549096 585656
163497 9...

output:

99964397555

result:

ok single line: '99964397555'

Test #40:

score: 40
Accepted
time: 182ms
memory: 6820kb

input:

200000 200000
659252 817322
793117 256613
791357 393725
322225 908846
342712 465130
580320 101256
983600 278515
44392 489265
323328 737062
55211 269726
90608 736295
713990 718813
3437 702588
58279 722836
539938 346523
130469 236837
74551 124448
418823 448084
434673 233891
324571 571753
164764 796458...

output:

99894127151

result:

ok single line: '99894127151'

Test #41:

score: 40
Accepted
time: 182ms
memory: 6704kb

input:

200000 200000
782202 605213
803779 239752
738070 327794
761458 124708
929105 732620
818782 900128
934794 798334
238198 677705
766367 209747
485755 889352
186764 948935
871104 1211
984438 702973
611286 478339
303841 864902
300097 480184
848566 573527
631402 521930
554261 214505
697417 891648
72485 26...

output:

100109588931

result:

ok single line: '100109588931'

Test #42:

score: 40
Accepted
time: 178ms
memory: 6756kb

input:

200000 200000
549613 451422
880336 86016
176158 875644
186887 123522
462758 375093
130521 321441
422540 996672
174236 358585
848661 398676
130937 756428
912198 727556
486494 944742
265166 666867
513878 217620
46779 753797
473113 33604
345543 730055
365903 656295
889446 842918
189174 481754
12302 579...

output:

100055140046

result:

ok single line: '100055140046'

Test #43:

score: 40
Accepted
time: 178ms
memory: 6708kb

input:

200000 200000
73851 282636
984416 870088
30252 72903
561514 942289
869675 467919
479912 402195
484522 761847
963506 568905
608577 379217
27072 19633
230594 148209
596477 474035
733943 743635
692056 828997
880436 939212
724200 860099
677166 519349
697010 739496
365543 119811
874527 528437
871847 9246...

output:

100281041056

result:

ok single line: '100281041056'