Pagini recente » Cod sursa (job #3135725) | Cod sursa (job #2200119) | Cod sursa (job #1264686) | Cod sursa (job #1011156) | Cod sursa (job #1853065)
#include<cstdio>
#include<algorithm>
using namespace std;
struct ura{
int st,dr,timp;};
ura v[100001],stiva[100001];
bool sortare (ura a, ura b){
if (a.st<b.st)
return a.st<b.st;
if (a.st==b.st)
return a.dr<b.dr;
return a.st<b.st;
}
int main()
{
freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
int n,i,j,pp=0;
scanf ("%d",&n);
for (i=1;i<=n;i++){
scanf ("%d%d",&v[i].st,&v[i].dr);
v[i].timp=v[i].dr-v[i].st;
}
sort (v+1,v+n+1,sortare);
int h=1,s,cate,ch;
stiva[1].st=v[1].st;
stiva[1].dr=v[1].dr;
stiva[1].timp=v[1].timp;
for(i=2;i<=n;i++)
{
if(v[i].st>=stiva[h].dr)
{
stiva[++h].st=v[i].st;
stiva[h].dr=v[i].dr;
stiva[h].timp=v[i].timp;
}
else
{
cate=0;
ch=h;
s=0;
//verificare
while(v[i].st<stiva[ch].st||(v[i].st>=stiva[ch].st&&v[i].st<=stiva[ch].dr))
{
cate++;
s+=stiva[ch].timp;
ch--;
}
if(v[i].timp>s)
{
h=ch;
stiva[++h].st=v[i].st;
stiva[h].dr=v[i].dr;
stiva[h].timp=v[i].timp;
}
}
}
s=0;
for(i=1;i<=h;i++)
s+=stiva[i].timp;
printf("%d",s);
return 0;
}