记录编号	411288	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]拆迁队	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.581 s
提交时间	2017-06-04 18:02:05	内存使用	7.17 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,ans1,a[N],b[N],d[N],g[N];
int rank(int *a,int x,int l,int r){
	while (l<r){
		int mid=(l+r)>>1;
		if (a[mid+1]<=x) l=mid+1;else r=mid;
	}
	return l;
}
typedef long double db;
ll dp[N],f[N];
ll cost(int i,int j){return dp[j]+ll(2*a[j]+i+j)*(i-j-1)/2;}
db K(int j,int k){
	if (a[j]==a[k]) return f[j]<f[k]?1e18:-1e18;
	return db(f[k]-f[j])/(a[k]-a[j]);
}
struct opt{int tp,i,lr;}Q[N],P[N];
//tp=1表示查询，tp=0表示插入
bool cmp(const opt &x,const opt &y){
	return a[x.i]==a[y.i]?x.tp<y.tp:a[x.i]<a[y.i];
}

int q[N],tail;
ll query(int id){
	int l=1,r=tail;
	if (r<l) return 1e18;
	while (l<r){
		int mid=(l+r)>>1;
		if (cost(id,q[mid])<cost(id,q[mid+1])) r=mid;else l=mid+1;
	}
	return cost(id,q[l])+a[id]+b[id]+id;
}
void push(int id){
	for (;tail>1&&K(q[tail-1],q[tail])>K(q[tail],id);tail--);
	q[++tail]=id;
}
void cdq(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	//归并排序
	for (int i=l;i<=mid;i++) Q[i].lr=0;
	for (int i=mid+1;i<=r;i++) Q[i].lr=1;
	int i=l,j=mid+1,p=l;
	while (i<=mid&&j<=r) P[p++]=cmp(Q[i],Q[j])?Q[i++]:Q[j++];
	for (;i<=mid;P[p++]=Q[i++]);
	for (;j<=r;P[p++]=Q[j++]);
	for (i=l;i<=r;i++) Q[i]=P[i];
	tail=0;
	for (i=l;i<=r;i++){
		int id=Q[i].i;
		if (!Q[i].lr&&!Q[i].tp) push(id);
		if (Q[i].lr&&Q[i].tp) dp[id]=min(dp[id],query(id));
	}
}
vector<int> v[N];
int main()
{
	freopen("lanxisi.in","r",stdin);
	freopen("lanxisi.out","w",stdout);
	scanf("%d",&n);
	v[0].push_back(0);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]-=i;
		if (a[i]<=-1) continue;
		d[i]=rank(g,a[i],0,ans1)+1;
		v[d[i]].push_back(i);
		if (d[i]>ans1) g[++ans1]=a[i];
		g[d[i]]=min(g[d[i]],a[i]);
	}
	for (int i=1;i<=n;i++) scanf("%d",&b[i]),dp[i]=1e18;
	for (int flag=0;flag<ans1;flag++){
		int i=0,j=0,size=0;
		vector<int> &a=v[flag],&b=v[flag+1];
		for (int i=0;i<a.size();i++){
			int id=a[i];
			f[id]=dp[id]-ll(2*::a[id]+id)*(id+1)/2;
		}
		while (i<a.size()&&j<b.size())
			Q[++size]=a[i]<b[j]?(opt){0,a[i++],0}:(opt){1,b[j++],0};
		for (;i<a.size();Q[++size]=(opt){0,a[i++],0});
		for (;j<b.size();Q[++size]=(opt){1,b[j++],0});
		cdq(1,size);
	}
	ll ans2=1e18;
	for (int i=1;i<=n;i++)
		if (d[i]==ans1) ans2=min(ans2,cost(n+1,i));
	printf("%d %lld\n",ans1,ans2);
	return 0;
}