记录编号	96853	评测结果	AAAAAAAAAA
题目名称	[USACO Feb14]登机	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	1.323 s
提交时间	2014-04-15 18:53:50	内存使用	43.02 MiB

//skip list 弱菜我只能膜拜WMD犇的代码学跳跃表
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int sizeN=200010,sizeH=25;
int N,tot=0,head=1,Ans=0;
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};
bool better(int tempx,int tempy){return B[tempx]-A[tempx]>=B[tempy]-A[tempy];}
int getH()
{
	for(int i=1;i<=sizeH;i++)
	{
		if(rand()%2)return i;
	}
	return sizeH;
}
void Downfloor(int H,int cow)
{
	if(!H)return;
	bool first=true;
	for(int x=cow;x!=next[H][cow];x=next[H-1][x])
	{
		if(!first)A[x]-=lazy[H][cow];
		first=false;
		lazy[H-1][x]+=lazy[H][cow];
	}
	lazy[H][cow]=0;
}
void work(int cow)
{
	tot++;
	A[tot]=S[cow];
	int x=head;
	for(int h=sizeH;h>=0;h--)
	{
		while(next[h][x] && A[next[h][x]]<S[cow])x=next[h][x];
		Downfloor(h,x);
	}
	int Sit=B[x]-A[x]+S[cow]+T[cow];
	B[tot]=Sit;
	Ans=max(Ans,Sit);
	x=head;
	A[x]--;
	int update_H=getH();//flip coins 随机出该点向上到第几层
	
	//该牛经过的所有限制都要--
	for(int h=sizeH;h>=0;h--)
	{
		while(next[h][x] && A[next[h][x]]<S[cow])
		{
			lazy[h][x]++;
			x=next[h][x];
			A[x]--;//经过的限制
		}
		Downfloor(h,x);
		while( next[h][x] && better(tot,next[h][x]) )
		{
			//删掉不优的限制
			Downfloor(h,next[h][x]);
			next[h][x]=next[h][next[h][x]];
		}
		if(update_H>=h)
		{
			//本层插入该点
			next[h][tot]=next[h][x];
			next[h][x]=tot;
		}
	}
	A[tot]--;
}
int main()
{
	freopen("boarding.in","r",stdin);
	freopen("boarding.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&S[i],&T[i]);
	tot++;
	for(int i=N;i>=1;i--)
		work(i);
	printf("%d\n",Ans);
	return 0;
}