Pagini recente » Cod sursa (job #1395264) | Cod sursa (job #977980) | Cod sursa (job #2166802) | Cod sursa (job #429223) | Cod sursa (job #2084225)
#include <bits/stdc++.h>
#define MAXN 100000
struct Interval{
int st, dr;
}v[1 + MAXN];
bool cmp(Interval A, Interval B){
return A.dr < B.dr;
}
int d[1 + MAXN];
int main(){
FILE*fi,*fo;
fi=fopen("heavymetal.in","r");
fo=fopen("heavymetal.out","w");
int n;
fscanf(fi,"%d", &n);
for(int i = 1; i <= n; i++)
fscanf(fi,"%d%d", &v[i].st, &v[i].dr);
std::sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; i++){
int ok = 0;
if(v[1].dr <= v[i].st){
int st = 1, dr = n - 1;
while(dr - st > 1){
int m = (st + dr) / 2;
if(v[m].dr > v[i].st)
dr = m - 1;
else
st = m;
}
if(v[dr].dr <= v[i].st)
ok = dr;
else
ok = st;
}
d[i] = std::max(d[i - 1], v[i].dr - v[i].st + d[ok]);
}
fprintf(fo,"%d", d[n]);
fclose(fi);
fclose(fo);
return 0;
}