QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#274924 | #7625. Path | ucup-team958# | WA | 139ms | 35936kb | C++14 | 2.7kb | 2023-12-04 07:52:47 | 2023-12-04 07:52:48 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
const int inf=1<<30;
const int maxn=100010;
const int MAXN=maxn<<2;
int a[maxn],b[maxn];
int da[MAXN],db[MAXN];
set<int>sa[maxn],sb[maxn];
int n,m,V;
void Adda(int i,int l,int r,int x,int k){
if(l==r){
sa[l].insert(k);
da[i]=*sa[l].begin();
return ;
}int mid=l+r>>1;
if(mid>=x) Adda(i<<1,l,mid,x,k);
else Adda(i<<1|1,mid+1,r,x,k);
da[i]=min(da[i<<1],da[i<<1|1]);
}
void Addb(int i,int l,int r,int x,int k){
if(l==r){
sb[l].insert(k);
db[i]=*sb[l].begin();
return ;
}int mid=l+r>>1;
if(mid>=x) Addb(i<<1,l,mid,x,k);
else Addb(i<<1|1,mid+1,r,x,k);
db[i]=min(db[i<<1],db[i<<1|1]);
}
void Dela(int i,int l,int r,int x,int k){
if(l==r){
sa[l].erase(k);
da[i]=*sa[l].begin();
return ;
}int mid=l+r>>1;
if(mid>=x) Dela(i<<1,l,mid,x,k);
else Dela(i<<1|1,mid+1,r,x,k);
da[i]=min(da[i<<1],da[i<<1|1]);
}
void Delb(int i,int l,int r,int x,int k){
if(l==r){
sb[l].erase(k);
db[i]=*sb[l].begin();
return ;
}int mid=l+r>>1;
if(mid>=x) Delb(i<<1,l,mid,x,k);
else Delb(i<<1|1,mid+1,r,x,k);
db[i]=min(db[i<<1],db[i<<1|1]);
}
int Qa(int i,int l,int r,int L,int R){
if(l>=L&&r<=R) return da[i];
if(l>R||r<L) return inf;
int mid=l+r>>1;
return min(Qa(i<<1,l,mid,L,R),Qa(i<<1|1,mid+1,r,L,R));
}
int Qb(int i,int l,int r,int L,int R){
if(l>=L&&r<=R) return db[i];
if(l>R||r<L) return inf;
int mid=l+r>>1;
return min(Qb(i<<1,l,mid,L,R),Qb(i<<1|1,mid+1,r,L,R));
}
ll calc(bool fl){
ll sum=0,sa=0;
int i=1,j=1,ni,nj;
while(i!=n||j!=m){
if(fl){
ni=Qa(1,1,V,a[i]+1,V),nj=Qb(1,1,V,b[j]+1,V);
if(ni==inf) ni=i; if(nj==inf) nj=j;
}
else{
ni=Qa(1,1,V,1,a[i]-1),nj=Qb(1,1,V,1,b[j]-1);
if(ni==inf) ni=i; if(nj==inf) nj=j;
}
if(i==ni&&j==nj&&sa) return sum;
for(int k=i;k<ni;k++) Dela(1,1,V,a[k],k);
for(int k=j;k<nj;k++) Delb(1,1,V,b[k],k);
sum+=abs(a[i]+b[j]-a[ni]-b[nj]);
sa=(i==ni&&j==nj),i=ni,j=nj;
fl^=1;
// printf("%d,%d\n",ni,nj);
}return sum;
}
void build(int i,int l,int r){
if(l==r){
da[i]=*sa[l].begin();
db[i]=*sb[l].begin();
return ;
}int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
da[i]=min(da[i<<1],da[i<<1|1]);
db[i]=min(db[i<<1],db[i<<1|1]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),V=max(V,a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]),V=max(V,b[i]);
for(int i=1;i<=V;i++) sa[i].insert(inf);
for(int i=1;i<=V;i++) sb[i].insert(inf);
build(1,1,V);
for(int i=1;i<=n;i++) Adda(1,1,V,a[i],i);
for(int i=1;i<=m;i++) Addb(1,1,V,b[i],i);
printf("%lld\n",max(calc(0),calc(1)));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 17124kb
input:
4 4 1 3 3 1 8 10 8 5
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 0ms
memory: 16624kb
input:
4 2 5 7 8 10 10 3
output:
12
result:
ok single line: '12'
Test #3:
score: -100
Wrong Answer
time: 139ms
memory: 35936kb
input:
100000 100000 18394 24233 357 52481 18043 49271 55052 81632 30068 16351 74661 71867 28721 46743 54031 18957 25470 94751 25746 62355 22561 5373 99009 49079 48551 48807 41085 90981 82649 23014 74376 54517 95181 9445 10083 85937 95809 31477 38527 68803 91671 55251 17894 43472 69255 20256 21718 38213 12...
output:
3339831541
result:
wrong answer 1st lines differ - expected: '6671609257', found: '3339831541'