Pagini recente » Cod sursa (job #347522) | Cod sursa (job #2807401) | Cod sursa (job #636526) | Cod sursa (job #211173) | Cod sursa (job #470518)
Cod sursa(job #470518)
#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);
for (i=j=1;j<=n;i++)
{
v[i]=v[i-1];
t[++t[0]]=a[j].y;
for (;a[j].y==t[i] && j<=n;j++)
v[i]=max(v[i],v[bs(a[j].x)]+a[j].y-a[j].x);
}
out<<v[t[0]]<<"\n";
return 0;
}