Pagini recente » Cod sursa (job #3181063) | Cod sursa (job #471067) | Cod sursa (job #320251) | Cod sursa (job #488560) | Cod sursa (job #1860862)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct eu {int st,dr;};
eu v[100010];
int s[100010];
int poz[100010];
bool cmp (eu a, eu b)
{
if(a.st<b.st)
return true;
if(a.st>b.st)
return false;
if(a.st==b.st)
{
if(a.dr<b.dr)
return true;
return false;
}
}
int main()
{
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int maxx=0,i,nr=0,pz,j,st,dr,mij,ans=0,n;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].st>>v[i].dr;
sort(v+1,v+n+1,cmp);
poz[1]=1;
s[1]=1;
nr=1;
for(i=2;i<=n;i++)
{
if(v[i].st>maxx)
{
nr++;
s[nr]=i;
maxx=v[i].dr;
poz[i]=nr;
}
else
{
st=1;
dr=nr;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij].dr>v[i].st)
dr=mij-1;
else
st=mij+1;
}
poz[i]=mij;
s[mij]=i;
}
}
int k=nr;
for(i=n;i>=1;i--)
{
if(poz[i]==k)
{
k--;
ans+=v[i].dr-v[i].st;
}
}
fout<<ans;
return 0;
}