Cod sursa(job #2505594)

Utilizator IsacLucianIsac Lucian IsacLucian Data 7 decembrie 2019 08:34:17
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 1e5+2;

int n, k;

struct Interval
{
    int a, b;

    bool operator < (const Interval &e) const
    {
        return b < e.b;
    }

}t[Nmax], dp[Nmax];

int Caut_bin(int x)
{
    int st, dr, mij, pos;
    st = 1; dr = k; pos = k;

    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (dp[mij].a <= x)
        {
            pos = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    return pos;
}

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> t[i].a >> t[i].b;

    sort(t + 1, t + n + 1);

    int x, y, p;

    for (int i = 1; i <= n; i++)
    {
        x = t[i].a;
        y = t[i].b;

        p = Caut_bin(x);

        if (dp[k].a == y)
            dp[k].b = max(dp[k].b, dp[p].b + y - x);
        else
        {
            k ++;
            dp[k].a = y;
            dp[k].b = max(dp[k - 1].b, dp[p].b + y - x);
        }
    }

    fout << dp[k].b << "\n";

    fin.close();
    fout.close();
    return 0;
}