比赛 20110729 评测结果 AAAAAAAAAAAA
题目名称 最后的利益 最终得分 100
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-29 08:55:15
显示代码纯文本
#include <cstdio>
#include <set>
#include <map>
using namespace std;

const int MAXN=50005;

struct Node
{
	int v;
	Node *next;
	void *operator new (size_t,void *p){return p;}
	Node(){}
	Node(int _v,Node *_next):v(_v),next(_next){}
}*adj[MAXN],pool[MAXN],*mem=pool;

inline void addedge(int u,int v)
{
	adj[u]=new (mem++)Node(v,adj[u]);
}

set<int> hash;
map<int,int> trans,rtrans;
int N;
int L[MAXN],R[MAXN];
int d[MAXN];

int main()
{
	freopen("9cwy.in","r",stdin);
	freopen("9cwy.out","w",stdout);
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%d%d",L+i,R+i);
		if (L[i]!=R[i])
		{
			hash.insert(L[i]);
			hash.insert(R[i]);
		}
	}
	int tot=0;
	for(set<int>::iterator it=hash.begin();it!=hash.end();it++)
	{
		trans[*it]=++tot;
		rtrans[tot]=*it;
	}
	for(int i=0;i<N;i++)
	{
		L[i]=trans[L[i]],R[i]=trans[R[i]];
		if (L[i]!=R[i])
			addedge(R[i],L[i]);
	}
	d[0]=0;
	for(int i=1;i<=tot;i++)
	{
		d[i]=d[i-1];
		int t=0;
		for(Node *p=adj[i];p;p=p->next)
			if ((t=d[p->v]+rtrans[i]-rtrans[p->v])>d[i])
				d[i]=t;
	}
	printf("%d\n",d[tot]);
	return 0;
}