Cod sursa(job #1857601)

Utilizator tgm000Tudor Mocioi tgm000 Data 26 ianuarie 2017 14:07:49
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
struct interval{int a,b,l;};
interval v[100001];
set <int> s;
set <int>::iterator it;
int d[200001];
bool cmp(interval x,interval y){
    if(x.b<y.b)
        return true;
    else
        return false;
}
int main(){
    int n,i,k,kk;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&v[i].a,&v[i].b);
        v[i].l=v[i].b-v[i].a;
        s.insert(v[i].a);
        s.insert(v[i].b);
    }
    for(i=1;i<=n;i++){
        v[i].a=distance(s.begin(),s.find(v[i].a))+1;
        v[i].b=distance(s.begin(),s.find(v[i].b))+1;
    }
    sort(v+1,v+n+1,cmp);
    k=1;
    it=s.end();
    it--;
    for(i=1;i<=s.size();i++){
        d[i]=d[i-1];
        while(v[k].b<i&&k<=n)
            k++;
        kk=k;
        while(v[kk].b==i){
            if(d[v[kk].a]+v[kk].l>d[i])
                d[i]=d[v[kk].a]+v[kk].l;
            kk++;
        }
    }
    printf("%d",d[s.size()]);
    return 0;
}