Cod sursa(job #1862288)

Utilizator adystar00Bunea Andrei adystar00 Data 29 ianuarie 2017 18:57:53
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct prb {int st,dr,timp;};
prb d[100001],v[100001];
bool cmp (prb a, prb b)
{
    return a.dr<b.dr;
}
int main()
{
    ifstream fin ("heavymetal.in");
    ofstream fout ("heavymetal.out");
    int i,n,st,dr,mij,pp;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].st>>v[i].dr;
        v[i].timp=v[i].dr-v[i].st;
    }
    sort(v+1,v+n+1,cmp);
    d[1].st=v[1].st;
    d[1].dr=v[1].dr;
    d[1].timp=v[1].timp;
    for(i=2;i<=n;i++)
    {
        if(v[i].st<d[i-1].dr)
        {
            st=0;
            dr=i-2;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(d[mij].dr<=v[i].st)
                {
                    pp=0;
                    st=mij+1;
                }
                else
                {
                    pp=1;
                    dr=mij-1;
                }
            }
            if(pp==1)
                mij--;
            if(d[mij].timp+v[i].timp>d[i-1].timp)
            {
                d[i].st=d[i-1].st;
                d[i].dr=v[i].dr;
                d[i].timp=v[i].timp+d[mij].timp;
            }
            else
            {
                d[i].st=d[i-1].st;
                d[i].dr=d[i-1].dr;
                d[i].timp=d[i-1].timp;
            }
        }
        else
        {
            d[i].st=d[i-1].st;
            d[i].dr=v[i].dr;
            d[i].timp=d[i-1].timp+v[i].timp;
        }
    }
    fout<<d[n].timp;
    return 0;
}