记录编号	537931	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.469 s
提交时间	2019-07-18 22:13:46	内存使用	6.11 MiB

#include<bits/stdc++.h>
#define ls(x) (t[x].ch[0])
#define rs(x) (t[x].ch[1])
using namespace std;
const int N=1e5+7;
const int INF=0x7f7f7f7f;
int m,n,k,ans,sum,cnt,root=0,x,y,z;
struct node
{
	int pri,ch[2],size,val;
} t[N];
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void push_up(int x){t[x].size=t[ls(x)].size+t[rs(x)].size+1;}
int new_node(int x) {t[++cnt].size=1;t[cnt].pri=rand();t[cnt].val=x;return cnt;}
int merge(int x,int y)
{
	if (!x||!y) return x+y;
	if  (t[x].pri<t[y].pri){rs(x)=merge(rs(x),y);push_up(x);return x;}
	else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}
void split(int now,int k,int &x,int &y)
{
	if (!now) x=0,y=0;
	else
	{
		if (t[now].val<=k) x=now,split(rs(now),k,rs(now),y);
		else y=now,split(ls(now),k,x,ls(now));
		push_up(now);
	}
}
int K_th(int now,int k)
{
	while (true)
	{
		if (k<=t[ls(now)].size) now=ls(now);
		else if (k==t[ls(now)].size+1) return now;
		else k-=t[ls(now)].size+1,now=rs(now);
	}
}
void insert(int a)
{
	split(root,a,x,y);
	root=merge(merge(x,new_node(a)),y);
}
int query(int a)
{
	split(root,a-1,x,y);int p=t[K_th(x,t[x].size)].val;merge(x,y);
	split(root,a-1,x,y);int q=t[K_th(y,1)].val;merge(x,y);
	if (abs(p-a)<abs(q-a)) return abs(p-a);
	else return abs(q-a);
}
int main()
{
	freopen("turnover.in","r",stdin);
	freopen("turnover.out","w",stdout);
	srand((unsigned)time(NULL));
	n=read();insert(-INF);insert(INF);
	for (int i=1;i<=n;i++)
	{
		int x=read();if (i==1) {insert(x);ans+=x;continue;}
		ans+=query(x);insert(x);
	}
	printf("%d",ans);
	return 0;
}