Pagini recente » Cod sursa (job #2065284) | Cod sursa (job #1841264) | Cod sursa (job #162190) | Cod sursa (job #1785702) | Cod sursa (job #1223050)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 100003;
struct band {
int left, right;
};
bool operator < (const band &a, const band &b) {
if (a.right < b.right)
return 1;
if (a.right == b.right)
return a.left < b.left;
return 0;
}
band V[NMAX];
int sel[NMAX], D[NMAX];
int binarySearch (int right, const int &val) {
int left = 1, middle;
while (left < right) {
middle = left + right >> 1;
if (V[sel[middle]].right <= val)
left = middle + 1;
else
right = middle;
}
return left;
}
int main () {
freopen ("heavymetal.in", "r", stdin);
freopen ("heavymetal.out", "w", stdout);
int N, i, j, k;
scanf ("%d", &N);
for (i = 1; i <= N; ++i)
scanf ("%d%d", &V[i].left, &V[i].right);
sort (V + 1, V + N + 1);
sel[1] = 1;
D[1] = V[1].right - V[1].left;
for (i = j = 2; i <= N; ++i, ++j) {
if (V[sel[j - 1]].right <= V[i].left) {
sel[j] = i;
D[j] = D[j - 1] + V[i].right - V[i].left;
}
else {
k = binarySearch (j - 1, V[i].left);
if (D[j - 1] - D[k - 1] < V[i].right - V[i].left) {
j = k;
D[j] = D[j - 1] + V[i].right - V[i].left;
sel[j] = i;
}
}
}
printf ("%d", D[j - 1]);
}