Pagini recente » Cod sursa (job #2345040) | Cod sursa (job #1765246) | Cod sursa (job #1366659) | Cod sursa (job #2903776) | Cod sursa (job #1217895)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define nmax 100005
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct interval {
int x,y;
};
int n,i,x,M;
int L[nmax];
interval A[nmax];
bool cmp(interval a, interval b) {
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
int bs(int hi) {
int lo = 1, maxim = 0, mid;
while (hi>=lo) {
mid = (hi + lo) >> 1;
if (A[i].x < A[mid].y)
hi = mid - 1;
else
maxim = max(maxim, L[mid]),
lo = mid + 1;
}
return maxim;
}
int main() {
in >> n;
for (i=1; i<=n; i++)
in >> A[i].x >> A[i].y;
sort(A+1, A+n+1, cmp);
L[1] = A[1].y - A[1].x;
M = L[1];
for (i=2; i<=n; i++)
x = bs(i-1),
L[i] = A[i].y - A[i].x,
L[i] = max(L[i], L[i]+x),
M = max(M, L[i]);
out << M << "\n";
return 0;
}