Pagini recente » Cod sursa (job #1103329) | Cod sursa (job #2396459) | Cod sursa (job #1007386) | Cod sursa (job #1305491) | Cod sursa (job #166313)
Cod sursa(job #166313)
#include <cstdio>
#include <algorithm>
using namespace std;
#define FIN "heavymetal.in"
#define FOUT "heavymetal.out"
#define MAX_N 100010
typedef struct
{
int x, y;
} interv;
interv A[MAX_N];
int B[MAX_N];
int N, i;
struct cmp
{
bool operator () (const interv &a, const interv &b) const
{
if (a.y < b.y) return 1;
return 0;
}
};
int binary (int v)
{
int li = 1, lf = N, m;
while (li <= lf)
{
m = (li + lf) >> 1;
if (A[m].y == v) break;
if (A[m].y > v) lf = m - 1;
else li = m + 1;
}
while (A[m].y > v) return m - 1;
return m;
}
void solve ()
{
int i;
for (i = 1; i <= N; ++i)
{
int crt = binary (A[i].x);
while (A[B[crt]].y == A[B[crt + 1]].y) ++crt;
B[i] = B[i - 1];
if (B[crt] + A[i].y - A[i].x > B[i])
B[i] = B[crt] + A[i].y - A[i].x;
}
printf ("%d\n", (int) B[N]);
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d", &N);
for (i = 1; i <= N; ++i) scanf ("%d %d", &A[i].x, &A[i].y);
sort (A + 1, A + N + 1, cmp());
solve ();
return 0;
}