记录编号	390429	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1859.[国家集训队2011]拆迁队	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.946 s
提交时间	2017-04-03 06:18:17	内存使用	5.25 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,INF=0x3f3f3f3f;
struct Rabit_tree{int to,next;}e[maxn];
int n,g[maxn],st[maxn],cot,num[maxn];LL A[maxn],B[maxn],f[maxn];
void Rabit_in(){
	R_int(n);int i,x;
	for(i=1;i<=n;i++)R_int(x),A[i]=x;
	for(i=1;i<=n;i++)R_int(x),B[i]=x;
}
void Rabit_bl(){
	int i,j;memset(g,-1,sizeof(g));f[0]=g[0]=0;
	for(i=1;i<=n;i++)
	for(j=0;j<i;j++)
		if(i-j<=A[i]-A[j]&&g[j]>=0){
			if(g[j]+1>g[i])g[i]=g[j]+1,
				f[i]=f[j]+A[i]+B[i]+(i-j)*1ll*(i-j-1)/2ll+A[j]*1ll*(i-j-1);
			else if(g[j]+1==g[i])
				f[i]=min(f[i],f[j]+A[i]+B[i]+(i-j)*1ll*(i-j-1)/2ll+A[j]*1ll*(i-j-1));
		}
	int ans1=0;LL ans2;
	for(i=1;i<=n;i++)
		if(g[i]>ans1)ans1=g[i],ans2=f[i]+A[i]*1ll*(n-i)+(n-i+1)*1ll*(n-i)/2ll;
		else if(g[i]==ans1)ans2=min(ans2,f[i]+A[i]*1ll*(n-i)+(n-i+1)*1ll*(n-i)/2ll);
	printf("%d %lld\n",ans1,ans2);
}
int c[maxn],head[maxn],len=1;
void Set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len;
}
void Add(int i,int x){
	for(;i<=cot;i+=i&(-i))c[i]=max(c[i],x);
}
int Get(int i){
	int res=-INF;for(;i;i-=i&(-i))res=max(res,c[i]);return res;
}
#define to e[i].to
void Rabit_sb(){
	int i,rt,ans1=0;LL ans2=1e20;
	for(i=0;i<=n;i++)st[++cot]=A[i]-i;
	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,A[i]-i)-st;
	for(i=1;i<=cot;i++)c[i]=-INF;
	Add(num[0],g[0]),Set(g[0],0);
	for(rt=1;rt<=n;rt++){
		g[rt]=Get(num[rt])+1,Add(num[rt],g[rt]),f[rt]=1ll<<50;
		if(g[rt]>0){
			for(i=head[g[rt]-1];i;i=e[i].next)
				if(num[rt]>=num[to])
				f[rt]=min(f[rt],
				f[to]+A[rt]+B[rt]+(rt-to)*1ll*(rt-to-1)/2ll+A[to]*1ll*(rt-to-1));
				Set(g[rt],rt);
		}
	}
	ans1=Get(cot);
	for(i=head[ans1];i;i=e[i].next)
		ans2=min(ans2,f[to]+A[to]*1ll*(n-to)+(n-to+1)*1ll*(n-to)/2ll);
	printf("%d %lld\n",ans1,ans2);
}
int main(){
	freopen("lanxisi.in","r",stdin);freopen("lanxisi.out","w",stdout);
	Rabit_in();//Rabit_bl();
	Rabit_sb();
	fclose(stdin);fclose(stdout);return 0;
}