记录编号	89910	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	Lunatic	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2014-03-04 16:51:13	内存使用	2.92 MiB

#include<cstdio>
#define Puts(x) printf("%d\n",x)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define N 2<<16
#define INF 2147483647
int n,Tot=0,del,root;
int s[N][2]={0},X[N],h[N],T=0;
char str[1000000],*p=str;

inline int abs(int x){return (x<0)?(-x):x;}
inline int New(int x){X[++Tot]=x;h[Tot]=0;return Tot;}
inline void Upd(int x){h[x]=max(h[s[x][0]],h[s[x][1]])+1;}
inline int Rt(int x,bool r){
       int k=s[x][r];
       s[x][r]=s[k][1-r];s[k][1-r]=x;
       Upd(x);Upd(k);
       return k;
}
inline void Ins(int&x,int u){
        if(!x) {x=New(u);return;}
        del=min(del,abs(u-X[x])); 
        if(u==X[x]) return;
        bool r=(u>X[x])?(1):(0);
        Ins(s[x][r],u);
        if(h[s[x][r]]-h[s[x][1-r]]==2){
            bool p=(u>X[s[x][r]])?(1):(0);
            if(p^r) s[x][r]=Rt(s[x][r],1-r);
            x=Rt(x,r);  
        }
        Upd(x);
        return;
}
inline int Gets(){
       int res=0;bool k;
	   while(*p!='-'&&(*p<'0'||*p>'9')) p++;
	   for(k=*p=='-'&&p++;'0'<=*p&&*p<='9';) res=res*10+*p++-48;
	   return k?-res:res;
}
int main(){
    freopen("turnover.in","r",stdin);
    freopen("turnover.out","w",stdout);
    fread(p,1,1000000,stdin);
    int x,A;
    n=Gets();
    n--,x=Gets(),A=x,root=New(x);
    while(n--){
        x=Gets();del=INF;
        Ins(root,x);
        A+=del;
    }
    Puts(A);
    return 0;
}