//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 的格式要求是 "插入 [该代码片段的中文名]"

{
    "土地征用 Land Acquisition": {
        "prefix": "acm-5.1min",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register LL",
            "const int N=5e4+5;",
            "struct QAQ{LL L,W;inline bool operator<(QAQ p)const{return W<p.W;}}a[N];",
            "LL i,j,n,m,h=1,t=0,H=1,T,L[N],W[N],Q[N],dp[N];",
            "inline LL min(Re a,Re b){return a<b?a:b;}",
            "inline LL X(Re j){return -L[j+1];}",
            "inline LL Y(Re j){return dp[j];}",
            "inline long double slope(Re i,Re j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}",
            "int main(){",
            "    scanf(\"%lld\",&m);",
            "    for(i=1;i<=m;++i)scanf(\"%lld%lld\",&a[i].L,&a[i].W);",
            "    std::sort(a+1,a+m+1);",
            "    for(i=1;i<=m;++i){",
            "    \twhile(1<=n&&L[n]<=a[i].L)--n;",
            "    \tL[++n]=a[i].L,W[n]=a[i].W;",
            "\t}",
            "    Q[++t]=0;",
            "    for(i=1;i<=n;++i){",
            "        while(h<t&&slope(Q[h],Q[h+1])<W[i])++h;",
            "        dp[i]=dp[j=Q[h]]+L[j+1]*W[i];",
            "        while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i))--t;",
            "        Q[++t]=i;",
            "    }",
            "    printf(\"%lld\",dp[n]);",
            "}",
            ""
        ],
        "description": "插入 土地征用 Land Acquisition"
    }
}