Cod sursa(job #1227744)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 11 septembrie 2014 15:55:51
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.h>
#include<algorithm>
#define N 100000
struct elem{int start;int end;} v[N];
bool cmp(elem a, elem b){
    if(a.start<b.start)
        return true;
    if(a.start>b.start)
        return false;
    if(a.end<a.end)
        return true;
    else return false;
}
int best[N];
inline int bsearch(int dr){
    int st=0,mij=(st+dr)/2,max=0,poz=dr+1;
    while(st<=dr){
        if(v[poz].start<v[mij].end)
            dr=mij-1;
        else{
            if(v[mij].end<=v[poz].start)
                max=mij;
            st=mij+1;
        }
        mij=(st+dr)/2;
    }
    return best[max];
}
inline int maxof2(int a,int b){
    if(a<b)
        return b;
    return a;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    int n;
    fscanf(fin,"%d",&n);
    int i;
    for(i=0;i<n;i++){
        fscanf(fin,"%d%d",&v[i].start,&v[i].end);
        v[i].start--,v[i].end--;
    }
    std::sort(v,v+n,cmp);
    best[0]=v[0].end-v[0].start;
    for(i=1;i<n;i++){
        int poz=bsearch(i-1);
        best[i]=maxof2(best[i-1],v[i].end-v[i].start+poz);
    }
    fprintf(fout,"%d",best[n-1]);
    return 0;
}