Pagini recente » Cod sursa (job #1766509) | Cod sursa (job #291704) | Cod sursa (job #1868194) | Borderou de evaluare (job #2238862) | Cod sursa (job #470464)
Cod sursa(job #470464)
#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<=n && a[i+step].y<x)
i+=step;
return i+1;
}
int bsrc(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=1;i<=t[0];i++)
{
v[i]=v[i-1];
for (j=bs(t[i]);a[j].y==t[i];j++)
v[i]=max(v[i],v[bsrc(a[j].x)]+a[i].y-a[i].x);
}
out<<v[t[0]]<<"\n";
return 0;
}