QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420314#8370. T3C1942huangjiaxu11 58ms7752kbC++141.1kb2024-05-24 16:28:492024-05-24 16:28:50

Judging History

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

  • [2024-05-24 16:28:50]
  • 评测
  • 测评结果:11
  • 用时:58ms
  • 内存:7752kb
  • [2024-05-24 16:28:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int n,m,a[N],b[N],va,vb,pa,pb,h[N];
ll s[N];
ll bf(int i,int j,int d){
	ll res=0;
	for(int k=1;k<=i;++k)res+=min(j,h[k]);
	for(int k=i+1;k<=n;++k)res+=m-max(j,h[k]);
	return res;
}
bool check(int d){
	ll mx1=0,mx2=0,v;
	for(int i=0,j=m;i<=n;++i){
		v=1ll*i*j+1ll*(n-i)*(m-j);
		mx1=max(mx1,v);
		mx2=max(mx2,v-(pa<=i&&pb<=j||pa>i&&pb>j));
		while(j&&a[i+1]+b[j]>d)--j;
		h[i+1]=j;
		v=1ll*i*j+1ll*(n-i)*(m-j);
		mx1=max(mx1,v);
		mx2=max(mx2,v-(pa<=i&&pb<=j||pa>i&&pb>j));
		//printf("%lld %lld %lld %d %d %d %d %d\n",v,mx1,mx2,d,i,j,pa,pb);
	}
	mx2=max(mx2,bf(pa,pb-1,d));
	mx2=max(mx2,bf(pa-1,pb,d));
	return mx1!=mx2+1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=m;++i)scanf("%d",&b[i]);
	va=a[1],vb=b[1];
	sort(a+1,a+n+1);
	sort(b+1,b+m+1);
	pa=lower_bound(a+1,a+n+1,va)-a;
	pb=lower_bound(b+1,b+m+1,vb)-b;
	int l=1,r=va+vb;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5844kb

input:

3 4
5793102 5457652 10631669
14037022 24564522 19828638 16740187

output:

19494674

result:

wrong answer 1st numbers differ - expected: '19830124', found: '19494674'

Subtask #2:

score: 11
Accepted

Test #11:

score: 11
Accepted
time: 20ms
memory: 6360kb

input:

58907 56480
44575563 540879 28467036 43621838 25515388 10048620 4501896 38628765 39419406 29497118 41954017 917402 20191987 40236908 12585166 22986979 1764011 21587278 32837245 20261107 20671792 37064770 22652008 6411880 34950023 5163325 17409659 46335787 11065741 6440463 44544150 13934453 19477226 ...

output:

23107969

result:

ok 1 number(s): "23107969"

Test #12:

score: 11
Accepted
time: 47ms
memory: 7004kb

input:

189469 57603
28875640 6205004 21110951 23480849 10442288 1789266 29632233 2628015 1177308 14489813 11239759 18891059 18357357 30758696 25588314 22649200 22717678 14167578 9873586 28217823 17553393 22985060 22126753 15538086 23430634 14333822 29323385 6702484 18708803 24043666 22202322 14747587 38164...

output:

15556246

result:

ok 1 number(s): "15556246"

Test #13:

score: 11
Accepted
time: 34ms
memory: 6896kb

input:

99777 187389
19763944 21503578 41516016 21554274 9822891 567461 38237030 4371484 31707886 31971273 11497457 37719395 38945202 19636623 35568861 12534068 42265227 44615432 22929766 25841774 9050837 17516300 1345745 29756960 15389514 40185177 477641 47018456 41868553 31966448 22785241 19288642 1998459...

output:

19763945

result:

ok 1 number(s): "19763945"

Test #14:

score: 11
Accepted
time: 22ms
memory: 6324kb

input:

113160 47525
1276933 22789424 8557545 24124072 5673143 19349986 6068519 24223576 19109679 18298197 16972903 5167574 14125432 23729490 13713930 2121302 754829 7698084 24601313 7612890 25983767 326845 13635128 7986662 19461362 430983 2015164 5552620 13672574 18313257 22573688 13289557 23248995 6111760...

output:

1276934

result:

ok 1 number(s): "1276934"

Test #15:

score: 11
Accepted
time: 54ms
memory: 6860kb

input:

194299 192720
11471195 17731923 28848736 20668135 21536730 19400122 14601810 2411273 15025095 13041786 2589289 14081383 9010694 25808670 16152489 27645649 5945099 4742052 6345608 10888556 27404345 888365 23499757 12483915 20348368 18362060 29583766 21929309 24663619 24190963 28967536 8747238 2345400...

output:

11471196

result:

ok 1 number(s): "11471196"

Test #16:

score: 11
Accepted
time: 52ms
memory: 6644kb

input:

193880 185453
79780189 32196116 13230026 20507797 73926538 17558792 31362493 71730754 3553784 68854833 24295672 17980905 8513267 70310779 61865777 53321876 8319154 2363610 75415155 75664646 74507662 81624645 55926408 23802257 48216702 24208145 24680172 57518874 799354 69525528 80525431 61239653 3199...

output:

41244548

result:

ok 1 number(s): "41244548"

Test #17:

score: 11
Accepted
time: 58ms
memory: 7752kb

input:

199509 196173
76819693 6001416 38675337 26574800 65693385 71887748 68966336 66961014 38686305 16698977 6384723 7970176 15667622 63907722 68921778 59778161 17837085 64013178 40230571 57187419 28336911 54349850 28825359 31883802 13981396 24672020 74114713 74597265 65433802 13002830 12801750 56964670 4...

output:

41896792

result:

ok 1 number(s): "41896792"

Test #18:

score: 11
Accepted
time: 28ms
memory: 6412kb

input:

190423 197347
54 46 8 43 2 42 4 54 60 40 36 56 38 31 18 7 14 32 42 32 37 6 41 31 12 30 48 43 29 36 31 53 38 51 39 47 51 60 48 18 43 33 1 38 56 59 11 49 53 44 21 60 42 24 49 43 1 45 19 26 33 55 20 11 11 36 23 4 3 19 31 56 53 27 41 36 22 8 60 13 58 35 15 21 54 57 53 43 54 8 29 56 52 60 18 21 55 58 17 ...

output:

32

result:

ok 1 number(s): "32"

Test #19:

score: 11
Accepted
time: 56ms
memory: 6632kb

input:

194522 195000
62071029 43865048 26267497 3905375 49244519 87362029 1407250 9637827 5279514 2376215 68376435 29472925 51497228 60308217 57325853 79704463 80653694 14098513 4549378 35008395 38597349 16827966 80493967 63448301 12631171 62857 76061937 33308915 57069618 6234363 73265515 80191500 60912489...

output:

43945085

result:

ok 1 number(s): "43945085"

Test #20:

score: 11
Accepted
time: 51ms
memory: 6412kb

input:

187417 194003
8405638 77105297 25566654 17758001 38339497 46536914 78507135 54302236 561280 58442113 45951883 47131131 19225639 23759327 56115386 16577425 68551695 86222622 75348727 29628027 77913322 2487406 79014793 55586652 46984320 20213167 87040338 57314257 51426353 19171567 79733971 64682558 27...

output:

8405639

result:

ok 1 number(s): "8405639"

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 15
Accepted
time: 1ms
memory: 6024kb

input:

3 10
24332538 25602471 54833728
7466852 20176810 23770883 13240181 15036268 16178071 19850557 11751859 12686516 11159532

output:

31799390

result:

ok 1 number(s): "31799390"

Test #22:

score: 15
Accepted
time: 0ms
memory: 5968kb

input:

4 9
14880669 10667567 7977836 1882967
80951479 5481207 15459896 52525030 28052486 14797866 34391066 58754229 27619130

output:

38286697

result:

ok 1 number(s): "38286697"

Test #23:

score: 15
Accepted
time: 1ms
memory: 5984kb

input:

6 5
1410209 331777 605947 756537 156780 131599
28694381 10823646 29868509 9541258 22217924

output:

22549701

result:

ok 1 number(s): "22549701"

Test #24:

score: 15
Accepted
time: 0ms
memory: 6032kb

input:

3 5
33150575 18966713 53782786
75149226 71799373 74419028 54775540 74124930

output:

107275505

result:

ok 1 number(s): "107275505"

Test #25:

score: 15
Accepted
time: 1ms
memory: 5996kb

input:

9 10
19770622 8756949 16056411 11314884 23189424 1141953 12422403 37892 22866723
42545625 10308121 21601490 30152072 2098306 10621367 15283148 17471310 27597062 53676957

output:

33527721

result:

ok 1 number(s): "33527721"

Test #26:

score: 15
Accepted
time: 0ms
memory: 5900kb

input:

10 9
3611512 3233156 3377069 553994 113187 2503076 1914585 2356051 1587266 2721722
11741545 3095423 1962742 4767129 9529924 11878991 5227734 15138953 3007732

output:

8378641

result:

ok 1 number(s): "8378641"

Test #27:

score: 0
Wrong Answer
time: 1ms
memory: 5980kb

input:

9 10
5208009 9307010 2051682 4944638 17253966 9060047 19420506 10885128 3584042
16054166 12616174 35594631 103757 37681867 39254477 25977857 44547227 50538254 6630288

output:

20998804

result:

wrong answer 1st numbers differ - expected: '21262175', found: '20998804'

Subtask #4:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 1ms
memory: 6032kb

input:

557 24
944055 6651285 6872647 7501680 6728901 5684173 78312 872911 5349349 5834868 1104965 5034609 943636 6298640 4862332 6874311 4925018 7027588 6656184 1303888 1092633 6129416 3629195 5717171 4703294 6929327 6147793 2666674 4531679 3785633 7473654 274978 7723474 1969517 3520566 5338238 380308 7691...

output:

36598012

result:

wrong answer 1st numbers differ - expected: '41467742', found: '36598012'

Subtask #5:

score: 0
Wrong Answer

Test #47:

score: 0
Wrong Answer
time: 1ms
memory: 5920kb

input:

557 24
944055 6651285 6872647 7501680 6728901 5684173 78312 872911 5349349 5834868 1104965 5034609 943636 6298640 4862332 6874311 4925018 7027588 6656184 1303888 1092633 6129416 3629195 5717171 4703294 6929327 6147793 2666674 4531679 3785633 7473654 274978 7723474 1969517 3520566 5338238 380308 7691...

output:

36598012

result:

wrong answer 1st numbers differ - expected: '41467742', found: '36598012'

Subtask #6:

score: 0
Wrong Answer

Test #64:

score: 0
Wrong Answer
time: 1ms
memory: 5984kb

input:

557 24
944055 6651285 6872647 7501680 6728901 5684173 78312 872911 5349349 5834868 1104965 5034609 943636 6298640 4862332 6874311 4925018 7027588 6656184 1303888 1092633 6129416 3629195 5717171 4703294 6929327 6147793 2666674 4531679 3785633 7473654 274978 7723474 1969517 3520566 5338238 380308 7691...

output:

36598012

result:

wrong answer 1st numbers differ - expected: '41467742', found: '36598012'