Pagini recente » Cod sursa (job #103710) | Cod sursa (job #292512) | Cod sursa (job #1269836) | Cod sursa (job #2854088) | Cod sursa (job #1972150)
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
struct Interval {
int x;
int y;
bool operator <(const Interval &other) const {
return this->y < other.y || (this->y == other.y && this->x < other.x);
}
};
Interval v[5 + MAX_N];
int d[5 + MAX_N];
int main() {
freopen ("heavymetal.in", "r", stdin);
freopen ("heavymetal.out", "w", stdout);
int n, st, dr, med, val, myMax;
scanf ( "%d", &n );
for (int i = 1; i <= n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
v[i].x = x;
v[i].y = y;
}
sort (v + 1, v + n + 1);
myMax = 0;
for (int i = 1; i <= n; ++i) {
st = 1;
dr = i;
val = v[i].x;
while (st < dr) {
med = (st + dr) / 2;
if (v[med].y <= val)
st = med + 1;
else
dr = med;
}
med = (st + dr) / 2;
if (v[med].y > val)
med--;
d[i] = max (d[med]+v[i].y-v[i].x, myMax);
if (d[i] > myMax)
myMax = d[i];
}
printf ("%d", myMax);
return 0;
}