Submission #67005302

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read(){
	char ch=getchar(); while(!isdigit(ch) && ch!='-') ch=getchar();
	int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
	return x*ff;
}
const int N=6e5+5;
int n,m;
LL a[N],b[N]; int s1[N],s2[N]; int stt[20][N];
inline int qmn(int l,int r) {int lm=__lg(r-l+1); return min(stt[lm][l],stt[lm][r-(1<<lm)+1]);}
bool chk(int kd){
	for(int i=1,j=0,k=0;i<=2*n;i++) {
		while(j<2*n && b[j+1]<a[i]) ++j;
		while(k<2*n && b[k+1]<=a[i]+kd) ++k;
		s1[i]=j; s2[i]=k;
	}
	for(int i=1;i<=2*n;i++) stt[0][i]=s2[i]-i;
	for(int i=1;(1<<i)<=2*n;i++)
		for(int j=1;j+(1<<i)-1<=2*n;j++) stt[i][j]=min(stt[i-1][j],stt[i-1][j+(1<<(i-1))]);
	for(int i=1,j=1;i<=n;i++){
		while(j+1<=2*n && a[j+1]+kd<a[i]+m) ++j;
		if(qmn(i,j)<s1[i]-i+1) return 0;
	}
	return 1;
}
void vmain(){
	n=read(); m=read();
	for(int i=1;i<=n;i++) a[i]=m-read();
	for(int i=1;i<=n;i++) b[i]=read();
	sort(a+1,a+n+1); sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) a[i+n]=a[i]+m,b[i+n]=b[i]+m;
	int L=-1,R=m-1;
	while(L+1<R){
		int mid=(L+R)/2;
		if(chk(mid)) R=mid;
		else L=mid;
	}
	printf("%d\n",R);
}
int main(){
	int T=read(); while(T--) vmain();
	return 0;
}

Submission Info

Judge Result