Pagini recente » Cod sursa (job #2237260) | Cod sursa (job #1314088) | Cod sursa (job #2958826) | Cod sursa (job #715315) | Cod sursa (job #1885785)
#include <stdio.h>
#include <algorithm>
#define MAX_N 100000
using namespace std;
int N;
int d[MAX_N + 1];
struct anakin{
int start, end;
};
anakin concert[MAX_N + 1];
bool cmp(anakin a, anakin b) {
return a.end >= b.end ? false : true;
}
int cautBin (int val) {
int x = 0;
int pas;
pas = 1 << 16;
while (pas) {
if (x + pas <= N && concert[x + pas].end <= val) {
x += pas;
}
pas >>= 1;
}
return x;
}
int main(){
FILE *fin = fopen("heavymetal.in", "r");
FILE *fout = fopen("heavymetal.out", "w");
int i;
int pos;
int pos_max = 0;
fscanf(fin, "%d", &N);
for (i = 1; i <= N; i++) {
fscanf(fin, "%d %d", &concert[i].start, &concert[i].end);
if (concert[i].end > pos_max)
pos_max = concert[i].end;
}
sort(concert + 1, concert + N + 1, cmp);
for (i = 1; i <= N; i++) {
pos = cautBin(concert[i].start);
d[concert[i].end] = d[concert[pos].end] + concert[i].end - concert[i].start;
}
fprintf(fout, "%d\n", d[pos_max]);
fclose(fin);
fclose(fout);
return 0;
}