记录编号	587149	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]拆迁队	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.930 s
提交时间	2024-03-15 18:53:31	内存使用	12.60 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
const ll inf = 1e17;
int n,cnt;
ll A[N],B[N],a[N],b[N],c[N];
ll f[N],g[N],ans,s = inf;
struct made{
    ll a,g;int id;
    int f,f2;
    bool operator < (const made x)const{
        return g < x.g;
    }
}w[N],s1[N],s2[N];
bool cmp1(made x,made y){
    return x.id < y.id;
}
bool cmp2(made x,made y){
    return x.a < y.a;
}


struct BIT{
    int c[N];
    inline int lowbit(int x){return x & (-x);}
    void clear(){memset(c,0,sizeof c);}
    void add(int x,int val){for(;x <= n+1;x += lowbit(x))c[x] = max(c[x],val);}
    int ask(int x){
        int ans = 0;
        for(;x > 0;x -= lowbit(x))ans = max(ans,c[x]+1);
        return ans;
    }
}t;


ll X(int x){return 2 * (A[x] - x);}
ll Y(int x){return (2*A[x] - x) * (x + 1) - 2 * f[x];}
int q[N],L,R;
void add(int x){
    int i = s2[x].id;
    while(L < R && (Y(q[R]) - Y(q[R-1])) * (X(i) - X(q[R])) <= (X(q[R]) - X(q[R-1])) * (Y(i) - Y(q[R])))R--;//Y打成X 调了4h 
    q[++R] = i;
}
int find(int x,int l,int r){
    while(l < r){
        int mid = l + r >> 1;
        if((Y(q[mid+1]) - Y(q[mid])) > x * (X(q[mid+1]) - X(q[mid])))l = mid+1;
        else r = mid;
    }
    return q[l];
}//二分 
void ask(int x){
    if(L <= R){
        int i = s2[x].id,j = find(s2[x].id,L,R);
        f[i] = min(f[i],f[j] + (2*A[j]+i-j)*(i-j-1)/2+b[i]);
    }
}
void CDQ(int l,int r){
    if(l == r)return;
    int mid = l + r >> 1;
    CDQ(l,mid);
    //
    L = 1,R = 0;
    for(int i = l;i <= r;i++){
        s1[i].f2 = (i > mid);
        s2[i] = s1[i];
    }
    sort(s2+l,s2+r+1,cmp2);
    for(int i = l;i <= r;i++){
        if(!s2[i].f && !s2[i].f2)add(i);
        if(s2[i].f && s2[i].f2)ask(i);
    }
    CDQ(mid+1,r);
}
int main(){
	freopen("lanxisi.in","r",stdin);
    freopen("lanxisi.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%lld",&A[i]),a[i] = A[i] - i,c[i] = a[i];
    for(int i = 1;i <= n;i++)scanf("%lld",&B[i]),b[i] = A[i] + B[i];
    sort(c+1,c+2+n);
    int m = unique(c+1,c+2+n) - (c+2);
    for(int i = 1;i <= n;i++){
        if(a[i] < 0){g[i]= -1;continue;}
        int x = lower_bound(c+1,c+1+m,a[i])-c;
        g[i] = t.ask(x);
        t.add(x,g[i]);
        ans = max(g[i],ans);
    }
    w[n+1] = {0,0,0,0,0};//额外的0号结点 
    for(int i = 1;i <= n;i++)f[i] = inf,w[i] = {a[i],g[i],i,0,0};
    
    
    sort(w+1,w+2+n);
    for(int i = 1;i <= n+1;i++){
        if(w[i].g == -1 || w[i].g == ans)continue;
        cnt = 0;
        for(int j = i;w[j].g <= w[i].g + 1 && j <= n+1;j++){
            s1[++cnt] = w[j];
            if(w[j].g == w[i].g)s1[cnt].f = 0;
            else s1[cnt].f = 1;
        }//根据g分层dp 
        sort(s1+1,s1+cnt+1,cmp1);
        CDQ(1,cnt);
        int j = i;
        for(j = i;w[j].g == w[i].g && j <= n+1;j++);
        i = j-1;
    }
    for(int i = 1;i <= n;i++)
        if(g[i] == ans)s = min(s,f[i]+(A[i]+1+n+a[i]) * (n-i) / 2);
    printf("%lld %lld\n",ans,s);

	return 0;

}