记录编号	106091	评测结果	AAAAAAAAAA
题目名称	[SGU U313]环形铁路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.227 s
提交时间	2014-06-13 09:47:06	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll SIZEN=50010;
ll N,L;
ll modN(ll x){
	x=x%N;
	if(x<=0) x+=N;
	return x;
}
ll modL(ll x){
	x=x%L;
	if(x<=0) x+=L;
	return x;
}
class BD{//建筑物
public:
	ll pos;//位置
	ll id;//编号
};
bool operator < (BD a,BD b){
	return a.pos<b.pos;
}
ll upper(BD *s,ll x,ll l,ll r){//第一个位置不小于x的
	if(l==r) return l;
	ll mid=(l+r)>>1;
	if(s[mid].pos>=x) return upper(s,x,l,mid);
	else return upper(s,x,mid+1,r);
}
ll upper(BD *s,ll x){//第一个不小于x的
	x=modL(x);
	if(s[N].pos<x) return 1;
	return upper(s,x,1,N);
}
ll lower(BD *s,ll x,ll l,ll r){//最后一个位置不大于x的
	if(l==r) return l;
	ll mid=(l+r)>>1;
	if(s[mid+1].pos<=x) return lower(s,x,mid+1,r);
	else return lower(s,x,l,mid);
}
ll lower(BD *s,ll x){//最后一个不大于x的
	x=modL(x);
	if(s[1].pos>x) return N;
	return lower(s,x,1,N);
}
ll event[SIZEN]={0};//当x1对应yi时,比对应yi-1多出的部分
BD X[SIZEN],Y[SIZEN];
ll matchx[SIZEN]={0};
ll dist(ll a,ll b){//xa~yb
	ll t=abs(X[a].pos-Y[b].pos);
	return min(t,L-t);
}
ll simulate(ll k){
	ll ans=0;
	ll i=1;
	while(i<=N){
		matchx[X[i].id]=Y[k].id;
		ans+=dist(i,k);
		i++,k++;
		if(k>N) k-=N;
	}
	return ans;
}
void work(void){
	ll ans=simulate(1),ansp=1;
	ll now=ans;
	for(ll i=2;i<=N;i++){
		now+=event[i];
		if(now<ans) ans=now,ansp=i;
	}
	printf("%lld\n",simulate(ansp));
	//for(ll i=1;i<=N;i++) printf("%lld ",matchx[i]);printf("\n");
}
void prepare_X(void){//我们把所有的L都算在X这边
	for(ll i=1;i<=N;i++){
		ll a=X[i].pos,t;
		if(a*2<=L){//位于前半段
			t=upper(Y,1);//当xi对应yt时,i的贡献从L+a变成了a
			//此时x1对应y(t-(i-1))
			event[modN(t-(i-1))]-=L;
			t=upper(Y,a);//当xi对应yt时,i的贡献从a变成了-a
			event[modN(t-(i-1))]-=2*a;
			t=upper(Y,a+(L+1)/2);//当xi对应yt时,i的贡献从-a变成了L+a
			event[modN(t-(i-1))]+=L+2*a;
		}
		else{//位于后半段
			t=upper(Y,1);//当xi对应yt时,i的贡献从-a变成了L-a
			event[modN(t-(i-1))]+=L;
			t=upper(Y,a-L/2);//当xi对应yt时,i的贡献从L-a变成了a
			event[modN(t-(i-1))]+=2*a-L;
			t=upper(Y,a);//当xi对应yt时,i的贡献从a变成了-a
			event[modN(t-(i-1))]-=2*a;
		}
	}
}
void prepare_Y(void){
	for(ll i=1;i<=N;i++){
		ll b=Y[i].pos,t;
		if(b*2<=L){
			t=lower(X,b);//当yi对应xt时,i的贡献从-b变成了b
			event[modN(i-(t-1))]+=2*b;
			t=lower(X,b+(L-1)/2);//当yi对应xt时,i的贡献从b变成了-b
			event[modN(i-(t-1))]-=2*b;
		}
		else{
			t=lower(X,b-(L+2)/2);//当yi对应xt时,i的贡献从b变成了-b
			event[modN(i-(t-1))]-=2*b;
			t=lower(X,b);//当yi对应xt时,i的贡献从-b变成了b
			event[modN(i-(t-1))]+=2*b;
		}
	}
}
void read(void){
	scanf("%lld%lld",&N,&L);
	for(ll i=1;i<=N;i++) scanf("%lld",&X[i].pos),X[i].id=i;
	for(ll i=1;i<=N;i++) scanf("%lld",&Y[i].pos),Y[i].id=i;
	sort(X+1,X+1+N);
	sort(Y+1,Y+1+N);
}
int main(){
	freopen("circularrailway.in","r",stdin);
	freopen("circularrailway.out","w",stdout);
	read();
	prepare_X();
	prepare_Y();
	work();
	return 0;
}