记录编号	419623	评测结果	AAAAAAAAAA
题目名称	[HNOI 2002]营业额统计	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2017-07-02 21:42:24	内存使用	0.56 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x7f000000;

inline char getc(void){ 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int in(void){ 
    register char tmp = getc();
    register int res = 0, f = 1;
    while(!isdigit(tmp) && tmp ^ EOF && tmp ^ '-') tmp = getc();
    if(tmp == EOF) return 0;
    if(tmp == '-') f = -1, tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res * f;
}

struct NODE{ 
    int s, height;
    NODE *ls, *rs;

    NODE(int x){ 
        ls = rs = NULL;
        height = 1;
        s = x;
    }

    int hgt(void){ 
        if(this) return height;
        return 0;
    }
};

inline void Left(NODE *&k2);
inline void Right(NODE *&k2);
void Insert(NODE *&node, int x);
inline int Pre(int x);
inline int Next(int x);

NODE *root;
int N, tmp;
int ans;

int main(){ 
#ifndef LOCAL
    freopen("turnover.in", "r", stdin);
    freopen("turnover.out", "w", stdout);
#endif
    N = in();
    ans = in();
    Insert(root, ans);
    for(int i = 2, a; i <= N; ++i){ 
        tmp = in();
        ans += (a = min(tmp - Pre(tmp), Next(tmp) - tmp));
        Insert(root, tmp);
    }

    printf("%d", ans);

    return 0;
}

inline void Left(NODE *&k2){ 
    register NODE *k1 = k2->ls;
    k2->ls = k1->rs;
    k1->rs = k2;

    k2->height = max(k2->ls->hgt(), k2->rs->hgt()) + 1;
    k1->height = max(k1->ls->hgt(), k1->rs->hgt()) + 1;
    k2 = k1; return ;
}

inline void Right(NODE *&k2){ 
    register NODE *k1 = k2->rs;
    k2->rs = k1->ls;
    k1->ls = k2;

    k2->height = max(k2->ls->hgt(), k2->rs->hgt()) + 1;
    k1->height = max(k1->ls->hgt(), k1->rs->hgt()) + 1;
    k2 = k1; return ;
}

void Insert(NODE *&node, int x){ 
    if(node){ 
        if(x < node->s){ 
            Insert(node->ls, x);
            if(node->ls->hgt() - node->rs->hgt() == 2){ 
                if(node->ls->ls->hgt() < node->ls->rs->hgt()) Right(node->ls);
                Left(node);
            } else node->height = max(node->ls->hgt(), node->rs->hgt()) + 1;
        } else if(node->s < x){
            Insert(node->rs, x);
            if(node->rs->hgt() - node->ls->hgt() == 2){ 
                if(node->rs->rs->hgt() < node->rs->ls->hgt()) Left(node->rs);
                Right(node);
            } else node->height = max(node->ls->hgt(), node->rs->hgt()) + 1;
        }
    } else node = new NODE(x);
    return ;
}

inline int Pre(int x){
    register int ans = -INF;
    register NODE *node = root;
    
    while(node){
        if(node->s == x) return node->s;
        if(node->s > x) node = node->ls;
        else {
            ans = node->s;
            node = node->rs;
        }
    }
 
    return ans;
}
 
inline int Next(int x){
    register int ans = INF;
    register NODE *node = root;
 
    while(node){
        if(node->s == x) return node->s;
        if(node->s < x) node = node->rs;
        else {
            ans = node->s;
            node = node->ls;
        }
    }
 
    return ans;
}