Cod sursa(job #2815094)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 9 decembrie 2021 07:41:36
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

struct trupa
{
    int st,dr,nrant = 0;
};

int n;
trupa a[100005];

int cb(int p)
{
    int dr = n + 1,pas = 1 << 16;
    while (pas != 0)
    {
        if (dr - pas >= 1 and dr - pas <= n and a[dr - pas].st >= p)
            dr -= pas;
        pas /= 2;
    }
    return dr;
}

int main()
{
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> a[i].st >> a[i].dr;
    sort(a + 1,a + n + 1,[](trupa A,trupa B){
         if (A.st != B.st)
            return A.st < B.st;
         return A.dr < B.dr;
         });
    for (int i = 1; i <= n; i++)
    {
        if (a[i].nrant < a[i - 1].nrant)
            a[i].nrant = a[i - 1].nrant;
        int pos = cb(a[i].dr);
        a[pos].nrant = max(a[pos].nrant,a[i].nrant + a[i].dr - a[i].st);
    }
    int maxim = 0;
    for (int i = 1; i <= n; i++)
        if (a[i].dr - a[i].st + a[i].nrant > maxim)
            maxim = a[i].dr - a[i].st + a[i].nrant;
    out << maxim;
    return 0;
}