Pagini recente » Cod sursa (job #1823683) | Cod sursa (job #1183106) | Cod sursa (job #1171327) | Cod sursa (job #165254) | Cod sursa (job #1122667)
#include<fstream>
#include<algorithm>
#define NMAX 100010
#define NRTIMPI 200010
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct formatie
{
int st, dr, x, y;
}a[NMAX];
int n, nr, timpi[NRTIMPI], best[NRTIMPI];
void Citeste()
{
int i, nr=0;
f>>n;
for (i=1; i<=n; ++i)
{
f>>a[i].x>>a[i].y;
timpi[++nr]=a[i].x;
timpi[++nr]=a[i].y;
}
}
int cauta(int x)
{
int st=1, dr=nr, mij;
while (st<=dr)
{
mij=(st+dr)/2;
if (timpi[mij]==x) return mij;
else
if (timpi[mij]>x) dr=mij-1;
else st=mij+1;
}
return 0;
}
void Normalizeaza()
{
int p=1, u=2, i;
sort(timpi+1, timpi+n+n+1);
while (u<=2*n)
if (timpi[p]==timpi[u]) ++u;
else
{
timpi[++p]=timpi[u]; ++u;
}
nr=p;
for (i=1; i<=n; ++i)
{
a[i].st=cauta(a[i].x);
a[i].dr=cauta(a[i].y);
}
}
bool cmp(formatie A, formatie B)
{
return A.dr<B.dr;
}
void Solve()
{
int i, j=1, lim=timpi[nr];
sort(a+1, a+n+1, cmp);
for (i=1; i<=lim; ++i)
{
best[i]=best[i-1];
while (a[j].dr==i)
{
best[i]=max(best[i], best[a[j].st]+a[j].y-a[j].x);
++j;
}
}
g<<best[lim]<<"\n";
}
int main()
{
Citeste();
Normalizeaza();
Solve();
f.close();
g.close();
return 0;
}