//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "营业额统计": {
        "prefix": "acm-2.7Treap",
        "body": [
            "#pragma GCC optimize(3,\"Ofast\",\"inline\")",
            "#pragma GCC optimize(2)",
            "#include<algorithm> ",
            "#include<cstdlib> ",
            "#include<cstdio>",
            "#include<ctime>",
            "#define Re register int",
            "#define pl tr[p].lp",
            "#define pr tr[p].rp",
            "#define pv tr[p].v",
            "using namespace std;",
            "const int N=32780,inf=2e9;",
            "int a,o,T,ans,root;",
            "inline void in(Re &x){",
            "    int fu=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')fu|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=fu?-x:x;",
            "}",
            "struct Treap{int v,rd,lp,rp,cnt,size;}tr[N];",
            "inline void pushup(Re p){tr[p].size=tr[p].cnt+tr[pl].size+tr[pr].size;}",
            "inline void lturn(Re &p){",
            "\tRe q=pr;pr=tr[q].lp,tr[q].lp=p;",
            "\tpushup(p),pushup(p=q);",
            "}",
            "inline void rturn(Re &p){",
            "\tRe q=pl;pl=tr[q].rp,tr[q].rp=p;",
            "\tpushup(p),pushup(p=q);",
            "}",
            "inline void insert(Re &p,Re x){",
            "\tif(!p){tr[p=++o].v=x,tr[p].cnt=tr[p].size=1,tr[p].rd=rand();return;}",
            "\t++tr[p].size;",
            "\tif(x==pv)++tr[p].cnt;",
            "\telse if(x<pv){",
            "\t\tinsert(pl,x);",
            "\t\tif(tr[pl].rd<tr[p].rd)rturn(p);",
            "\t}",
            "\telse{",
            "\t\tinsert(pr,x);",
            "\t\tif(tr[pr].rd<tr[p].rd)lturn(p);",
            "\t}",
            "}",
            "inline int ask_pri(Re p,Re x){",
            "\tif(!p)return -inf;",
            "\tif(x==pv)return x;",
            "\telse if(x<pv)return ask_pri(pl,x);",
            "\telse return max(pv,ask_pri(pr,x));",
            "}",
            "inline int ask_nex(Re p,Re x){",
            "\tif(!p)return inf;",
            "\tif(x==pv)return x;",
            "\telse if(x>pv)return ask_nex(pr,x);",
            "\telse return min(pv,ask_nex(pl,x));",
            "}",
            "int main(){",
            "\tsrand((int)time(NULL));",
            "\tin(T);--T;in(a);ans=a;insert(root,a);",
            "\twhile(T--){",
            "\t\tin(a);",
            "\t\tans+=min(abs(a-ask_pri(root,a)),abs(a-ask_nex(root,a)));",
            "\t\tinsert(root,a);",
            "\t}",
            "\tprintf(\"%d\",ans);",
            "}",
            ""
        ],
        "description": "插入 营业额统计"
    }
}