QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#419743#8590. Problem SetterJawad_Akbar#34 233ms11652kbC++20877b2024-05-24 10:46:332024-05-25 16:16:48

Judging History

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

  • [2024-05-25 16:16:48]
  • 管理员手动重测该提交记录
  • 测评结果:34
  • 用时:233ms
  • 内存:11652kb
  • [2024-05-24 10:46:33]
  • 提交

answer

#include <iostream>

using namespace std;
const int N = (1<<20) + 1;
int Mx[N<<1];

void insert(int i,int val,int cur = 1,int st = 1,int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		Mx[cur] = val;
		return;
	}

	int lc = cur + cur,rc = lc + 1,mid = (st + en) / 2;
	insert(i,val,lc,st,mid);
	insert(i,val,rc,mid,en);

	Mx[cur] = max(Mx[lc],Mx[rc]);
}

int get(int l,int r,int cur = 1,int st = 1,int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return Mx[cur];
	int lc = cur + cur,rc = lc + 1,mid = (st + en) / 2;
	return max(get(l,r,lc,st,mid),get(l,r,rc,mid,en));
}

int main(){
	int c,p;
	cin>>c>>p;

	for (int i=1,m,s;i<=c;i++){
		cin>>m>>s;
		insert(m,s);
	}

	long long ans = 0;

	for (int i=1,q,d;i<=p;i++){
		cin>>q>>d;
		ans += max(0,get(1,q+1) - d);
	}

	cout<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 18
Accepted

Test #1:

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

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: 0ms
memory: 11136kb

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: 0ms
memory: 11244kb

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: 0ms
memory: 11400kb

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: 3ms
memory: 11176kb

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: 0ms
memory: 11280kb

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: 3ms
memory: 11640kb

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: 0ms
memory: 11112kb

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: 3ms
memory: 11512kb

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: 0ms
memory: 11144kb

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: 7800kb

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: 3ms
memory: 11300kb

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: 3ms
memory: 11048kb

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: 11376kb

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: 3ms
memory: 11544kb

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: 3ms
memory: 11008kb

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: 0ms
memory: 11644kb

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: 3ms
memory: 11324kb

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: 0ms
memory: 11632kb

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: 0ms
memory: 10944kb

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: 3ms
memory: 11000kb

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: 7840kb

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: 1ms
memory: 7712kb

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: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 233ms
memory: 11652kb

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:

199981356288

result:

wrong answer 1st lines differ - expected: '199985649927', found: '199981356288'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%