Cod sursa(job #2641492)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 11 august 2020 17:25:38
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb

#include <bits/stdc++.h>
#define MAX 100001

using namespace std;
struct Interval
{
    int in;
    int sf;
    int l;
}v[MAX];

bool cmp(Interval a, Interval b)
{
    if(a.sf < b.sf)
        return true;
    if(a.sf == b.sf && a.in < b.in)
        return true;

    return false;
}

int main()
{
    int n;
    int answer = 0;

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

    fin >> n;

    for(int i = 0; i < n; i++)
        fin >> v[i].in >> v[i].sf;

    sort(v, v + n, cmp);

    for(int i = 0; i < n; i++)
    {
        int st = 0, dr = i - 1;

        while(st <= dr)
        {
            int mij = (st + dr) >> 1;

            if(v[mij].sf <= v[i].in)
                st = mij + 1;
            else
                dr = mij - 1;
        }

        v[i].l = v[i].sf - v[i].in;
        if(dr != -1)v[i].l += v[dr].l;
        v[i].l = max(v[i].l, v[i - 1].l);

        answer = max(answer, v[i].l);
    }

    fout << answer;

    return 0;
}