Cod sursa(job #2153571)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 6 martie 2018 12:12:50
Problema Heavy metal Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int i,d[100001],mid,dr,st,p,poz,n,maxi;
struct meme{
    int x,y;
}v[100001];
int cmp(meme a,meme b){
    if(a.x==b.x)
        return a.x<b.x;
    return a.y<b.y;
}
int main()
{   f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    d[1]=v[1].y-v[1].x;p=v[1].y;
    for(i=2;i<=n;i++){
        if(v[i].x>=p){
            d[i]=d[i-1]+v[i].y-v[i].x;
            p=v[i].y;
            if(maxi<d[i]){
                maxi=d[i];
                p=v[i].y;
            }
        }
        else{
            st=1;dr=i-1;poz=0;
            while(st<=dr){
                mid=(st+dr)/2;
                if(v[mid].y<=v[i].x){
                    st=mid+1;
                    poz=mid;
                }
                else
                    dr=mid-1;
            }
            d[i]=max(d[i-1],d[poz]+v[i].y-v[i].x);
            if(maxi<d[i]){
                maxi=d[i];
                p=v[i].y;
            }
        }
    }
    g<<maxi;
    return 0;
}