记录编号	443346	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2017-08-30 15:29:13	内存使用	1.45 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
map<int,int>ma;
int real_value[35000];
int mx[140005],mn[140005];
inline void pushup(int i){
	mx[i]=max(mx[i<<1],mx[i<<1|1]);
	mn[i]=min(mn[i<<1],mn[i<<1|1]);
}
inline void update(int pos,int w,int l,int r,int i){
	if(l==r){
		mx[i]=mn[i]=w;
		return;
	}
	int mid((l+r)>>1);
	if(pos<=mid)
		update(pos,w,l,mid,i<<1);
	else
		update(pos,w,mid+1,r,i<<1|1);
	pushup(i);
}
inline int query_mx(int ll,int rr,int l,int r,int i){//cout<<"max"<<ll<<' '<<rr<<' '<<l<<' '<<r<<' '<<i<<endl;
	if(ll<=l&&r<=rr)
		return mx[i];
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)
		ret=query_mx(ll,rr,l,mid,i<<1);
	if(mid<rr)
		ret=max(ret,query_mx(ll,rr,mid+1,r,i<<1|1));
	return ret;
}
inline int query_mn(int ll,int rr,int l,int r,int i){//cout<<"min"<<ll<<' '<<rr<<' '<<l<<' '<<r<<' '<<i<<endl;
	if(ll<=l&&r<=rr)
		return mn[i];
	int mid((l+r)>>1),ret(0x7fffffff);
	if(ll<=mid)
		ret=query_mn(ll,rr,l,mid,i<<1);
	if(mid<rr)
		ret=min(ret,query_mn(ll,rr,mid+1,r,i<<1|1));
	return ret;
}
int a[35000],tmp[35000];
int n;
int ans;
inline int jdz(int x){
	return x>=0?x:-x;
}
int inf;
inline int gg(){
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
	memset(mn,0x3f,sizeof(mn));
	inf=mn[1];
	n=read();
	for(int i=1;i<=n;++i)
		tmp[i]=a[i]=read();
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i)
		ma[a[i]]=i,real_value[i]=a[i];
	ans=tmp[1];
	update(ma[tmp[1]],ma[tmp[1]],1,n,1);
	for(int i=2;i<=n;++i){
		int pre(query_mx(1,ma[tmp[i]],1,n,1)),nxt(query_mn(ma[tmp[i]],n,1,n,1));
		if(nxt==inf)
			ans+=jdz(real_value[pre]-tmp[i]);
		else{
			if(pre==0)
				ans+=jdz(real_value[nxt]-tmp[i]);
			else
				ans+=min(jdz(real_value[pre]-tmp[i]),jdz(real_value[nxt]-tmp[i]));
		}
		update(ma[tmp[i]],ma[tmp[i]],1,n,1);
	}
	printf("%d",ans);
}
int K(gg());
int main(){;}