记录编号	96708	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14]登机	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.272 s
提交时间	2014-04-14 16:14:20	内存使用	43.04 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<list>
using namespace std;
const int SIZEN=200010,SIZEH=25,INF=0x7fffffff/2;
int S[SIZEN]={0},T[SIZEN]={0};
int next[SIZEH+1][SIZEN]={0},lazy[SIZEH+1][SIZEN]={0};//这两个是跳跃表
int A[SIZEN]={0},B[SIZEN]={0};//A是位置,B是时间
int N;
int tot=0,head=1;
void pushdown(int alt,int u){//高度为alt的节点u
	if(!alt) return;
	bool first=true;//这是因为上下一整列都对应一个A的下标
	for(int x=u;x!=next[alt][u];x=next[alt-1][x]){
		if(!first) A[x]-=lazy[alt][u];
		first=false;
		lazy[alt-1][x]+=lazy[alt][u];
	}
	lazy[alt][u]=0;
}
int getH(void){//1/2概率往上跳
	for(int i=0;i<SIZEH;i++) if(rand()&1) return i;
	return SIZEH;
}
bool better(int x,int y){
	return B[x]-A[x]>=B[y]-A[y];
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d%d",&S[i],&T[i]);
}
int ans=0;
void dealcow(int u){//第u只牛
	tot++;
	A[tot]=S[u];
	int height=getH();
	int x=head;
	for(int alt=SIZEH;alt>=0;alt--){
		while(next[alt][x]&&A[next[alt][x]]<S[u]) x=next[alt][x];
		pushdown(alt,x);
	}
	int V=B[x]-A[x]+S[u]+T[u];//V是该牛坐下的时间
	B[tot]=V;//新的限制
	ans=max(ans,V);
	x=head;
	A[x]--;
	for(int alt=SIZEH;alt>=0;alt--){//将这头牛经过的限制的A减一
		while(next[alt][x]&&A[next[alt][x]]<S[u]){
			lazy[alt][x]++;
			x=next[alt][x];
			A[x]--;
		}
		pushdown(alt,x);
		while(next[alt][x]&&better(tot,next[alt][x])){//删除元素
			pushdown(alt,next[alt][x]);
			next[alt][x]=next[alt][next[alt][x]];
		}
		if(height>=alt){//应当在本层插入新加上的限制节点
			next[alt][tot]=next[alt][x];
			next[alt][x]=tot;
		}
	}
	A[tot]--;//对于下一头牛应当这么做
}
void work(void){
	tot++;//限制1储存了(0,0)
	for(int i=N;i>=1;i--) dealcow(i);
	printf("%d\n",ans);
}
int main(){
	freopen("boarding.in","r",stdin);
	freopen("boarding.out","w",stdout);
	read();
	work();
	return 0;
}