记录编号	390891	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]拆迁队	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.958 s
提交时间	2017-04-04 15:56:10	内存使用	14.79 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char cc;inline void R_int(int &x){
	while(cc=getchar(),cc<'!');x=cc-48;
	while(cc=getchar(),cc>'!')x=x*10+cc-48;
}
#define LL long long
const int maxn=100005<<1,INF=0x3f3f3f3f;
struct Rabit_tree {int to,next;}e[maxn];
int n,st[maxn],cot,g[maxn],num[maxn],head[maxn],len=1,c[maxn],X[maxn];
LL A[maxn],B[maxn],f[maxn],Y[maxn];
void Set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len;
}
void Add(register int i,int x){
	for(;i;i-=i&(-i))c[i]=max(c[i],x);
}
int Get(register int i){
	int res=-INF;for(;i<=cot;i+=i&(-i))res=max(res,c[i]);return res;
}
#define to e[i].to
void Rabit_in(){
	R_int(n);int i,rt,x;
	for(i=1;i<=n;i++)R_int(x),A[i]=x,st[i]=i-A[i];
	for(i=1;i<=n;i++)R_int(x),B[i]=x;
	st[cot=n+1]=0,sort(st+1,st+cot+1),cot=unique(st+1,st+cot+1)-st-1;
	for(i=0;i<=n;i++)num[i]=lower_bound(st+1,st+cot+1,i-A[i])-st;
	for(i=1;i<=cot;i++)c[i]=-INF;
	Set(g[0]=0,0),Add(num[0],g[0]);
	for(rt=1;rt<=n;rt++){
		g[rt]=Get(num[rt])+1;
		if(g[rt]>0)Set(g[rt],rt),Add(num[rt],g[rt]);			
	}
}
int q[maxn],Dep,tmp[maxn],Q[maxn],s,t;
bool Cmp(int a,int b){
	if(num[a]==num[b])return g[a]<g[b];
	return num[a]>num[b];
}
double Get(int a,int b){return (Y[a]-Y[b])/(double)(X[a]-X[b]);}
LL Run(int x,int y){
	return f[y]+(x-y)*1ll*(x-y-1)/2ll+A[y]*1ll*(x-y-1);
}
bool Check(int a,int b,int c){
	if(num[a]==num[b])return Y[a]>=Y[b];
	return Get(c,a)>=Get(b,a);
}
void Dig(int x){
	if(s>t)return;
	int l=s,r=t-1,mid;double k=x;
	while(l<=r){
		mid=(l+r)>>1;
		if(Get(q[mid+1],q[mid])>=k)l=mid+1;else r=mid-1;
	}
	f[x]=min(f[x],Run(x,q[l]));
}
void Rabit_run(int l,int r){
	if(l==r){if(g[Q[l]]==Dep)f[Q[l]]+=B[Q[l]]+A[Q[l]];return;}
	int mid=(l+r)>>1,cnt=0,i;s=1,t=0;	
	for(i=l;i<=mid;i++)if(g[Q[i]]<Dep)tmp[cnt++]=Q[i];
	for(i=mid+1;i<=r;i++)if(g[Q[i]]==Dep)tmp[cnt++]=Q[i];
	sort(tmp,tmp+cnt,Cmp);
	for(i=0;i<cnt;i++)
		if(g[tmp[i]]<Dep){
			while(s<t&&Check(q[t-1],q[t],tmp[i]))t--;
			q[++t]=tmp[i];
		}
		else Dig(tmp[i]);
	Rabit_run(l,mid);Rabit_run(mid+1,r);
}
void Rabit_ans(){
	int res=Get(1),rt,i,cnt;LL ans=1ll<<50;
	for(rt=1;rt<=res;rt++){
		cnt=0;Dep=rt;
		for(i=head[rt-1];i;i=e[i].next)
			Q[++cnt]=to,X[to]=A[to]-to,
			Y[to]=-(f[to]+to*1ll*(to+1ll)/2ll-A[to]*(to+1ll));
		for(i=head[rt];i;i=e[i].next)Q[++cnt]=to,f[to]=ans;
		sort(Q+1,Q+cnt+1);Rabit_run(1,cnt);
	}
	for(i=head[res];i;i=e[i].next)
		ans=min(ans,f[to]+A[to]*1ll*(n-to)+(n-to+1)*1ll*(n-to)/2ll);
	printf("%d %lld\n",res,ans);
}
int main(){
	freopen("lanxisi.in","r",stdin);freopen("lanxisi.out","w",stdout);
	Rabit_in();Rabit_ans();
	fclose(stdin);fclose(stdout);return 0;
}