Cod sursa(job #2965992)

Utilizator Ion.AAlexandru Ion Ion.A Data 16 ianuarie 2023 17:33:06
Problema Heavy metal Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 100000;

struct trupa{
    int st, dr;
};
trupa v[N + 1];

int n, t[N + 1];
///t[i] = timpul maxim pentru intervalul care se termina in v[i].fn

bool cmp(trupa a, trupa b)
{
    return a.dr < b.dr;
}

int caut_bin(int poz)
{
    int st = 1, dr = n, last = 0;
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (v[mij].dr <= v[poz].st)
        {
            ///out << "\n" << "pentru trupa " << poz << " last-ul este " << last << " si are timpul " << v[last].dr - v[last].st << " si potentialul last este " << mij;
            if (v[mij].dr - v[mij].st >= v[last].dr - v[last].st)
            {
                last = mij;
            }
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    return last;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> v[i].st >> v[i].dr;
    }
    sort(v + 1, v + n + 1, cmp);
    t[0] = 0;
    /**for (int i = 1; i <= n; i++)
    {
        out << v[i].st << " " << v[i].dr << "\n";
    }
    */
    for (int i = 1; i <= n; i++)
    {
        ///caut binar cel mai bun interval cu v[k].dr <= v[i].st
        int ind = caut_bin(i);
        t[i] = t[ind] + (v[i].dr - v[i].st);
        ///out << "\n" << "am ajuns la trupa " << i << " pentru care cel mai bun interval este cel de pe pozitia " << ind << " si care are t-ul egal cu " << t[i] << ' ' << "\n";
    }
    out << t[n];
    return 0;
}