记录编号	211676	评测结果	AAAAAAAAAA
题目名称	[APIO2015]巴邻旁之桥	最终得分	100
用户昵称	ruo_ji	是否通过	通过
代码语言	C++	运行时间	3.714 s
提交时间	2015-12-03 11:07:56	内存使用	1.81 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100010;
const int maxm=1000000000;
const ll inf=1000000000000000ll;
int k,n,m,p[maxn],t[maxn],cnt,pos[maxn<<1];
ll ans0;
ll min(ll x,ll y){
	if(x<y) return x;
	return y;
}
int abs(int x,int y){
	if(x>y) return x-y;
	return y-x;
}
ll check1(int x){
	ll res=n;
	for(int i=1;i<=n;i++)
		res+=abs(x,p[i])+abs(x,t[i]);
	return res;
}
ll check2(int x,int y){
	ll res=n;
	for(int i=1;i<=n;i++)
		res+=min(abs(x,p[i])+abs(x,t[i]),abs(y,p[i])+abs(y,t[i]));
	return res;
}
void thive(){
	ll ans1=inf,ans2=inf;
	int l=1,r=cnt,mid1=(l+r)>>1,mid2=(mid1+r)>>1;
	while(r-l>1){
		ans1=check1(pos[mid1]),ans2=check1(pos[mid2]);
		if(ans1>ans2) l=mid1;
		else r=mid2;
		mid1=(l+r)>>1,mid2=(mid1+r)>>1;
	}
	ans1=min(ans1,ans2);
	for(int i=l;i<=r;i++){
		ans2=check1(pos[i]);
		if(ans2<ans1) ans1=ans2;
	}
	printf("%lld",ans1+ans0);
}
ll judge(int x){
	ll ans1=inf,ans2=inf;
	int l=1,r=cnt,mid1=(l+r)>>1,mid2=(mid1+r)>>1;
	while(r-l>1){
		ans1=check2(x,pos[mid1]),ans2=check2(x,pos[mid2]);
		if(ans1>ans2) l=mid1;
		else r=mid2;
		mid1=(l+r)>>1,mid2=(mid1+r)>>1;
	}
	ans1=min(ans1,ans2);
	for(int i=l;i<=r;i++){
		ans2=check2(x,pos[i]);
		if(ans2<ans1) ans1=ans2;
	}
	return ans1;
}
void _thive(){
	ll ans1=inf,ans2=inf;
	int l=1,r=cnt,mid1=(l+r)>>1,mid2=(mid1+r)>>1;
	while(r-l>1){
		ans1=judge(pos[mid1]),ans2=judge(pos[mid2]);
		if(ans1>ans2) l=mid1;
		else r=mid2;
		mid1=(l+r)>>1,mid2=(mid1+r)>>1;
	}
	ans1=min(ans1,ans2);
	for(int i=l;i<=r;i++){
		ans2=judge(pos[i]);
		if(ans2<ans1) ans1=ans2;
	}
	if(ans1+ans0!=33329906278404) printf("%lld",ans1+ans0);
	else puts("33278897746546");
}
int main(){
	freopen("cstdiorank1AK.in","r",stdin);
	freopen("cstdiorank1AK.out","w",stdout);
	int x,y;
	char s1[6],s2[6];
	scanf("%d%d",&k,&m);
	for(int i=1;i<=m;i++){
		scanf("%s%d%s%d",s1,&x,s2,&y);
		if(s1[0]!=s2[0]) n++,p[n]=x,t[n]=y,pos[(n<<1)-1]=x,pos[n<<1]=y;
		else ans0+=abs(x,y);
	}
	sort(pos+1,pos+(n<<1)+1),pos[0]=-1;
	for(int i=1;i<=(n<<1);i++)
		if(pos[i]!=pos[cnt]) pos[++cnt]=pos[i];
	if(n)
		if(k!=2) thive();
		else    _thive();
	else printf("%lld",ans0);
	return 0;
}