Cod sursa(job #2539815)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 6 februarie 2020 12:49:55
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct band{
    int s,d,t;
}a[100009];

int n;

bool comp(band a, band b)
{
    return a.s < b.s || a.s == b.s && a.d < b.d;
}

int BS(int s, int d, int index)
{
    if(s > d)
        return 0;
    int mid = (s+d)/2;
    if(a[mid].d <= a[index].s)
        return max(a[mid].t, BS(mid+1, d , index));
    else return BS(s, mid-1, index);
}

void Read()
{
    int i,j;
    int vmax = 0;
    fin>>n;
    for(i=1; i<=n; ++i)
    {
        fin>>a[i].s>>a[i].d;
    }
    sort(a+1, a+n+1, comp);
    a[1].t = a[1].d - a[1].s;
    for(i=2; i<=n; ++i)
    {
        int poz = BS(1, i-1 , i);
        a[i].t = a[poz].t + (a[i].d - a[i].s);
    }
    for(i=1; i<=n; ++i)
        if(a[i].t > vmax)
            vmax = a[i].t;
    fout<<vmax;
}

int main()
{
    Read();
    return 0;
}