Pagini recente » Borderou de evaluare (job #1489136) | Borderou de evaluare (job #2239788) | Borderou de evaluare (job #1837450) | Borderou de evaluare (job #738780) | Cod sursa (job #470516)
Cod sursa(job #470516)
#include <fstream>
using namespace std;
struct interval{int x,y;} a[1<<17];
int v[1<<17],t[1<<17],n;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
bool cmp(interval a,interval b)
{
return a.y<b.y || a.y==b.y && a.x<b.x;
}
int bs(int x)
{
int i,step=1<<16;
for (i=0;step;step>>=1)
if (i+step<=t[0] && t[i+step]<=x)
i+=step;
return i;
}
int main()
{
int i,j;
in>>n;
for (i=1;i<=n;i++)
in>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
t[1]=a[1].y;
for (i=t[0]=1;i<=n;i++)
if (a[i].y!=t[t[0]])
t[++t[0]]=a[i].y;
for (i=j=1;i<=t[0];i++)
{
v[i]=v[i-1];
for (;a[j].y==t[i];j++)
v[i]=max(v[i],v[bs(a[j].x)]+a[i].y-a[i].x);
}
out<<v[t[0]]<<"\n";
return 0;
}