QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420033 | #8370. T3 | by_chance | 0 | 95ms | 11792kb | C++14 | 1.6kb | 2024-05-24 14:09:50 | 2024-05-24 14:09:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,a[N],b[N],va,vb;
ll ca[N],cb[N],sa[N],sb[N],pa[N],pb[N];
int calc(ll x,ll y,ll lim,ll op){
ll res=0;
if(ca[x]>=y)res+=x*y;else res+=pa[y]*y+sa[x]-sa[pa[y]];
if(cb[y+1]>=n-x)res+=(n-x)*(m-y);
else res+=(m-pb[n-x]+1)*(n-x)+sb[y+1]-sb[pb[n-x]];
if(op)res-=(va<=x&&vb<=y&&a[va]+b[vb]<=lim),
res-=(va>x&&vb>y&&a[va]+b[vb]>lim);
return res;
}
bool check(int lim){
int p=m;
for(int i=1;i<=n;i++){
while(p&&a[i]+b[p]>lim)pa[p]=i-1,--p;
sa[i]=sa[i-1]+(ca[i]=p);
}
while(p)pa[p]=n,--p;
p=1;cb[m+1]=n+1;pb[n+1]=m+1;
for(int i=m;i>=1;i--){
while(p<=n&&a[p]+b[i]<=lim)pb[n-p+1]=i+1,++p;
sb[i]=sb[i+1]+(cb[i]=n-p+1);
}
while(p<=n)pb[n-p+1]=1,++p;
int res1=sb[1],res2=sb[1]-(a[va]+b[vb]>lim);
for(int i=1,p1=1,p2=1;i<=n;i++){
while(p1<m&&calc(i,p1,lim,0)<=calc(i,p1+1,lim,0))++p1;
while(p2<m&&calc(i,p2,lim,1)<=calc(i,p2+1,lim,1))++p2;
res1=max(res1,calc(i,p1,lim,0));res2=max(res2,calc(i,p2,lim,1));
}
return res1==res2;
}
int main(){
// freopen("chess.in","r",stdin);
// freopen("chess.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);va=a[1];
for(int i=1;i<=m;i++)scanf("%d",b+i);vb=b[1];
sort(a+1,a+n+1);va=lower_bound(a+1,a+n+1,va)-a;
sort(b+1,b+m+1);vb=lower_bound(b+1,b+m+1,vb)-b;
int L=0,R=a[va]+a[vb];
while(L<R){
int mid=(L+R)>>1;
if(check(mid))R=mid;else L=mid+1;
}
printf("%d\n",R);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3824kb
input:
3 4 5793102 5457652 10631669 14037022 24564522 19828638 16740187
output:
11250754
result:
wrong answer 1st numbers differ - expected: '19830124', found: '11250754'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 11
Accepted
time: 42ms
memory: 6976kb
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: 95ms
memory: 10716kb
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: 0
Wrong Answer
time: 93ms
memory: 11792kb
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:
0
result:
wrong answer 1st numbers differ - expected: '19763945', found: '0'
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 15
Accepted
time: 1ms
memory: 3964kb
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: 0
Wrong Answer
time: 0ms
memory: 3996kb
input:
4 9 14880669 10667567 7977836 1882967 80951479 5481207 15459896 52525030 28052486 14797866 34391066 58754229 27619130
output:
14880669
result:
wrong answer 1st numbers differ - expected: '38286697', found: '14880669'
Subtask #4:
score: 0
Wrong Answer
Test #34:
score: 0
Wrong Answer
time: 1ms
memory: 3956kb
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:
1131771
result:
wrong answer 1st numbers differ - expected: '41467742', found: '1131771'
Subtask #5:
score: 0
Wrong Answer
Test #47:
score: 0
Wrong Answer
time: 1ms
memory: 3840kb
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:
1131771
result:
wrong answer 1st numbers differ - expected: '41467742', found: '1131771'
Subtask #6:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 1ms
memory: 3976kb
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:
1131771
result:
wrong answer 1st numbers differ - expected: '41467742', found: '1131771'