Pagini recente » Cod sursa (job #1809060) | Cod sursa (job #1359227) | Cod sursa (job #1386403) | Cod sursa (job #1647707) | Cod sursa (job #234618)
Cod sursa(job #234618)
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[100010],B[100010];
int timp[100010],rez[100010];
int sir[100010],n;
long maxim;
struct cmp
{
bool operator()(const int a, const int b) const
{
return (B[a]<B[b]);
}
};
int cauta(int x,int poz)
{
int st=1,dr=poz,mij=0;
while (st<dr)
{
mij=(st+dr)>>1;
if (timp[mij]>x)
dr=mij;
else
st=mij+1;
}
while (timp[st]<=x)
st++;
if (timp[st-1]<=x)
return st-1;
return 0;
}
void calcul()
{
timp[1]=B[sir[0]];
rez[1]=B[sir[0]]-A[sir[0]];
maxim=rez[1];
for (int i=1;i<n;i++)
{
timp[i+1]=A[sir[i]]+1;
int j=cauta(A[sir[i]],i);
timp[i+1]=timp[i];
rez[i+1]=rez[i];
if (rez[i+1]<rez[j]+(B[sir[i]]-A[sir[i]]))
{
rez[i+1]=rez[j]+(B[sir[i]]-A[sir[i]]);
timp[i+1]=B[sir[i]];
maxim=rez[i+1];
}
}
printf("%ld\n",maxim);
}
int main ()
{
freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
scanf ("%d",&n);
for (int i=0;i<n;i++)
{
sir[i]=i;
scanf ("%d %d",&A[i],&B[i]);
}
sort(sir,sir+n,cmp());
calcul();
return 0;
}