Pagini recente » Cod sursa (job #1802564) | Cod sursa (job #2135238) | Cod sursa (job #2036210) | Cod sursa (job #906044) | Cod sursa (job #1384340)
#include <fstream>
#include <algorithm>
#define nmax 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interval{int x;int y;int z;};
int n,t,v[nmax],d[nmax*2];
interval r[nmax];
int cautbin(int x)
{
int p,q=0;
for (p=1<<19;p;p>>=1)
if (q+p<=t&&v[q+p]<=x)
q+=p;
if (v[q]==x)
return q;
return 0;
}
bool cmp(const interval &a, const interval &b)
{
return a.y<b.y;
}
int main()
{
int i,j;
f>>n;
for (i=1;i<=n;i++) {
f>>r[i].x>>r[i].y;
if (!cautbin(r[i].x))
v[++t]=r[i].x;
if (!cautbin(r[i].y))
v[++t]=r[i].y;
}
sort(v+1,v+t+1);
for (i=1;i<=n;i++) {
r[i].z=r[i].y-r[i].x;
r[i].x=cautbin(r[i].x);
r[i].y=cautbin(r[i].y);
}
sort(r+1,r+n+1,cmp);
j=1;
for (i=1;i<=t;i++) {
d[i]=max(d[i],d[i-1]);
while (j<=n&&r[j].y<i)
j++;
while (j<=n&&r[j].y==i) {
d[i]=max(d[i],d[r[j].x]+r[j].z);
j++;
}
}
g<<d[t]<<'\n';
return 0;
}