QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#274924#7625. Pathucup-team958#WA 139ms35936kbC++142.7kb2023-12-04 07:52:472023-12-04 07:52:48

Judging History

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

  • [2023-12-04 07:52:48]
  • 评测
  • 测评结果:WA
  • 用时:139ms
  • 内存:35936kb
  • [2023-12-04 07:52:47]
  • 提交

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'