[ZJ] a813. 2013高雄市能力競賽高中組 4. 城市觀測

#include<stdio.h>
#include<string.h>
int s[1000005],add[1000005]={0},add2[1000005]={0};
int sta[1000005],top=0;
int main(){
    int t,n,i,j,l,m,r;
    scanf("%d",&n);
    top=0;
    for(i=0;i<n;i++)
        scanf("%d",&s[i]);
    sta[top++]=s[0];
    for(i=1;i<n;i++){
        l=0,r=top;
        while(l+1!=r){
            m=(l+r)/2;
            if(sta[m]>s[i]) l=m;
            else r=m;
        }
        add[i]=top-l;
        while(top && s[i]>sta[top-1]) top--;
        sta[top++]=s[i];
    }
    long long int ans=0;
    for(i=0;i<n;i++){
        ans+=add[i]*2;
    }
    printf("%lld\n",ans);
}