怎么错的?
查看原帖
怎么错的?
161296
DarksideCoderω楼主2020/9/6 17:05
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename Type>inline Type Max(Type x,Type y){if(x>y)return x;return y;}
struct Node
{
	long long data,place;
	Node(){data=place=0;}
	bool operator>(Node a)
	{
		if(data==a.data)return place<a.place;
		else return data>a.data;
	}
};
inline Node NewNode(long long data,long long place)
{
	Node now;
	now.data=data;
	now.place=place;
	return now;
}
struct Segment_Tree
{
	Segment_Tree(){Clean();}
	const static long long MaxCnt=210000;
	long long cnt;
	long long Son[MaxCnt*4][2];
	Node Data[MaxCnt*4];
	long long Left[MaxCnt*4],Right[MaxCnt*4];
	inline void Clean()
	{
		cnt=0;
		memset(Son,0,sizeof(Son));
		memset(Left,0,sizeof(Left));
		memset(Right,0,sizeof(Right));
	}
	inline void Build(long long &now,long long left,long long right)
	{
		now=++cnt;
		Left[now]=left;Right[now]=right;
		if(left==right){Data[now]=NewNode(0,left);return;}
		else
		{
			long long mid=(left+right)/2;
			Build(Son[now][0],left,mid);
			Build(Son[now][1],mid+1,right);
			Data[now]=Max(Data[Son[now][0]],Data[Son[now][1]]);
		}
	}
	inline void Modify(long long now,long long pos,long long val)
	{
		if(Left[now]==Right[now]){Data[now].data=val;return;}
		else
		{
			long long mid=(Left[now]+Right[now])/2;
			if(pos<=mid)Modify(Son[now][0],pos,val);
			else Modify(Son[now][1],pos,val);
			Data[now]=Max(Data[Son[now][0]],Data[Son[now][1]]);
		}
	}
	inline Node Query(long long now,long long left,long long right)
	{
		if(left<=Left[now]&&Right[now]<=right)return Data[now];
		else
		{
			long long mid=(Left[now]+Right[now])/2;
			if(right<=mid)return Query(Son[now][0],left,right);
			else if(mid+1<=left)return Query(Son[now][1],left,right);
			return Max(Query(Son[now][0],left,right),Query(Son[now][1],left,right));
		}
	}
}ST;
long long n,root,ans;
long long L[201000];
long long R[201000];
long long Take[201000];
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
		L[i]=-n+i,scanf("%lld%lld",&R[i],&Take[i]);
	ST.Build(root,1,n);
	for(long long i=n;i>=1;i--)
	{
		Node tmp=ST.Query(root,1,R[i]);long long tot; 
		if(tmp.data==0)
		{
			ans=Max(ans,(tot=R[i]-L[i]+Take[i]));
			ST.Modify(root,R[i],tot+1);
		}
		else
		{
			ans=Max(ans,(tot=R[i]-tmp.place+Max(tmp.place-L[i],tmp.data)+Take[i]));
			ST.Modify(root,R[i],tot+1);
		}
	}
	printf("%lld",ans);
	return 0;
}
2020/9/6 17:05
加载中...