Cod sursa(job #1851797)

Utilizator DanaPalangean7A Daria Palangean DanaPalangean Data 20 ianuarie 2017 09:05:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<cstdio>
#include<algorithm>

using namespace std;

struct hm{
    int x, y, val;
};
hm v[100001];
int i, j, n, m, x, k;
bool sorting(hm a,hm b){
    return a.y<b.y;
}
int main(){
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d", &n);
    for(i=1;i<=n;i++)
        scanf("%d%d", &v[i].x, &v[i].y);
    sort(v+1,v+n+1,sorting);
    for(i=1;i<=n;i++){
        int l1=1, l2=i-1, y=0;
        while(l1<=l2){
            int mid=(l1+l2)/2;
            if(v[mid].y<=v[i].x){
                y=mid;
                l1=mid+1;
            }else
                l2=mid-1;
        }
        v[i].val=max(v[i-1].val,v[i].y-v[i].x+v[y].val);
    }
    printf("%d\n", v[n].val);
    return 0;
}