记录编号	348098	评测结果	AWAAAWWWWW
题目名称	[USACO Mar08] 土地购买	最终得分	40
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.344 s
提交时间	2016-11-13 21:22:25	内存使用	3.76 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long i64;
const int maxn=70010;
i64 w(int,int);
void build(i64*);
i64 qmax(int,int,i64*);
int n,M=1,q[maxn],l[maxn],r[maxn],head,tail;
i64 a[maxn<<1],b[maxn<<1],f[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("acquire.in","r",stdin);
	freopen("acquire.out","w",stdout);
#endif
	scanf("%d",&n);
	while(M<n+2)M<<=1;
	for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i+M],&b[i+M]);
	build(a);
	build(b);
	head=tail=1;
	q[1]=0;
	f[0]=0ll;
	l[1]=1;
	r[1]=n;
	for(int i=1;i<=n;i++){//printf("i=%d\n",i);
		if(l[head]<i)l[head]=i;
		if(r[head]<i)head++;
		f[i]=f[q[head]]+w(q[head],i);
		if(f[i]+w(i,n)>f[q[tail]]+w(q[tail],n))continue;
		int left=r[tail]+1;
		while(head<=tail&&f[i]+w(i,l[tail])<=f[q[tail]]+w(q[tail],l[tail]))left=l[tail--];
		if(head<=tail){
			int L=l[tail],R=n;
			while(L<=R){
				int M=(L+R)>>1;//printf("L=%d R=%d M=%d\n",L,R,M);
				if(f[i]+w(i,M)<f[q[tail]]+w(q[tail],M))L=M+1;
				else R=M-1;
			}
			left=L;
		}
		r[tail]=left-1;
		q[++tail]=i;
		l[tail]=left;
		r[tail]=n;
		//printf("i=%d queue:\n");
		//for(int i=head;i<=tail;i++)printf("x=%d l=%d r=%d\n",q[i],l[i],r[i]);
	}
	printf("%lld",f[n]);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
i64 w(int j,int i){
	return qmax(j+1,i,a)*qmax(j+1,i,b);
}
void build(i64 *a){
	for(int i=M-1;i;i--)a[i]=max(a[i<<1],a[i<<1|1]);
}
i64 qmax(int l,int r,i64 *a){
	i64 ans=1ll<<63;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=max(ans,a[l^1]);
		if(r&1)ans=max(ans,a[r^1]);
	}
	return ans;
}