Pagini recente » Cod sursa (job #634285) | Cod sursa (job #2729705)
#include <bits/stdc++.h>
#define dim 100002
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
long long nr[2*dim],dp[2*dim];
unordered_map<long long ,long long > asoc;
struct el
{
long long a,b;
}v[dim];
inline bool cmp (const el &a1,const el &a2)
{
if (a1.a==a2.a)
return a1.b<a2.b;
return a1.a<a2.a;
}
int main()
{
long long n,i,ct=1,j=1;
fin>>n;
for (i=1;i<=n;i++)
{
fin>>v[i].a>>v[i].b;
v[i].a++;
nr[2*i]=v[i].b;
nr[2*i-1]=v[i].a;
}
sort(nr+1,nr+2*n+1);
sort(v+1,v+n+1,cmp);
for (i=1;i<=2*n;i++)
if (nr[i]!=nr[i-1])
asoc[nr[i]]=ct++;
for (i=1;i<ct;i++)
{
dp[i]=max(dp[i],dp[i-1]);
while (asoc[v[j].a]==i && j<=n)
{
dp[asoc[v[j].b]]=dp[asoc[v[j].a]]+v[j].b-v[j].a+1;
++j;
}
}
fout<<dp[ct-1]<<'\n';
}