Pagini recente » Cod sursa (job #242000) | Cod sursa (job #162786) | Cod sursa (job #562353) | Cod sursa (job #1410868) | Cod sursa (job #223333)
Cod sursa(job #223333)
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define MAX_N 100005
#define DIM 8192
int N, logN;
long Bst[MAX_N];
int pz = DIM-1;
char buf[DIM];
struct met{long long li, lf;} V[MAX_N];
void read(long long &x)
{
x = 0;
while(!isdigit(buf[pz]))
if(++pz == DIM)
fread(buf, sizeof (char), DIM, stdin), pz = 0;
while(isdigit(buf[pz]))
{
x = x*10 + (buf[pz] - '0');
if(++pz == DIM)
fread(buf, sizeof (char), DIM, stdin), pz = 0;
}
}
void citire()
{
long long x;
read(x);
N = x;
for(int i = 1; i <= N; ++i)
{
read(V[i].li); read(V[i].lf);
}
}
struct cmp
{
bool operator()(const met a, const met b) const
{
return ((a.lf < b.lf) || (a.lf == b.lf) && (a.li < b.li));
}
};
long b_search(long x)
{
int i, lg;
for(i = 0, lg = logN; lg; lg >>= 1)
if(i + lg <= N && V[i + lg].lf <= x)
i += lg;
return i;
}
void solve()
{
sort(V+1, V+N+1, cmp());
for(logN = 1; logN <= N; logN <<= 1);
for(int i = 1; i <= N; ++i)
{
Bst[i] = Bst[i-1];
long poz = b_search(V[i].li);
long dif = V[i].lf - V[i].li;
if(Bst[poz] + dif> Bst[i])
Bst[i] = dif + Bst[poz];
}
printf("%ld\n",Bst[N]);
}
int main()
{
freopen("heavymetal.in","rt",stdin);
freopen("heavymetal.out","wt",stdout);
citire();
solve();
}