Cod sursa(job #2581894)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 15 martie 2020 23:33:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct band
{
    int start, fin;
    int t;
}a[100009];
int n;

void Read()
{
    int i;
    fin >> n;
    for(i=1; i<=n; ++i)
        fin >> a[i].start >> a[i].fin;
}

bool cr(band a, band b)
{
    ///ordonam crescator dupa timpul de inceput si daca timpurile de inceput sunt egale sortam crescator dupa timpul de final
    return a.fin < b.fin || a.fin == b.fin && a.start < b.start;
}

int CB(int st, int dr, int x)
{
    int poz=0, m;
    while(st<=dr)
    {
        m = (st+dr)/2;
        if(a[m].fin <= a[x].start)
        {
            poz = m;
            st = m + 1;
        }
        else dr = m - 1;
    }
    return poz;
}

void Solve()
{
    int i, vmax=0, poz;
    sort(a+1, a+n+1, cr);

    a[1].t = a[1].fin - a[1].start;
    for(i=2; i<=n; ++i)
    {
        a[i].t = a[i-1].t;
        poz = CB(1,i,i); ///vedem la cine dinainte poate fi adaugat
        //cout << poz << " " ;
        a[i].t =max(a[i].t, a[poz].t + (a[i].fin - a[i].start));
    }

    for(i=1; i<=n; ++i)
        if(a[i].t > vmax)
            vmax = a[i].t;
    fout << vmax << "\n";
}

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