记录编号	358367	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.073 s
提交时间	2016-12-15 23:22:33	内存使用	1.82 MiB

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <climits>
#define file(x) "turnover." #x
using std::min;
const int N = 1e5 + 10;
int n, st[N], nsz, rt, ch[N][2], fa[N], ans;
inline void lk(int x, int y, int d) {
	if (x) fa[x] = y;
	if (y) ch[y][d] = x;
}
inline int gd(int o) {return ch[fa[o]][1] == o;}
inline void rot(int o) {
	int x = fa[o], d = gd(o);
	lk(o, fa[x], gd(x));
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	if (x == rt) rt = o;
}
inline int newnode(int v) {
	st[++nsz] = v;
	return nsz;
}
void splay(int o) {
	for (int x; x = fa[o]; rot(o))
		if(fa[x]) rot(gd(o) == gd(x) ? x : o);
}
void insert(int o, int v) {
	for (int p; p = ch[o][v >= st[o]]; o = p) ;
	lk(newnode(v), o, v >= st[o]);
	splay(nsz);
}
int sp(int o, int t) {
	for (o = ch[o][t], t ^= 1; ch[o][t]; o = ch[o][t]) ;
	return o;
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d", &n);
	while (n--) {
		int x;
		if (scanf("%d", &x) == EOF) x = 0;
		if (rt) insert(rt, x);
		else rt = newnode(x);
		int a = sp(rt, 0), b = sp(rt, 1), d = INT_MAX;
		if (a) d = min(abs(st[a] - x), d);
		if (b) d = min(abs(st[b] - x), d);
		if (!a && !b) d = x;
		ans += d;
	}	
	printf("%d\n", ans);
}