Cod sursa(job #2784192)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 16 octombrie 2021 01:35:44
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;
const int NMAX = 100000;

struct seg
{
    int lo, hi;
};
struct repr
{
    int hi, maxlen;
};
struct cmpHeap
{
    public : bool operator()(const repr &a, const repr &b)
    {
        return a.hi > b.hi;
    };
};
bool cmpSort(seg a, seg b)
{
    return a.lo < b.lo;
}
seg shows[NMAX];
priority_queue<repr, vector<repr>, cmpHeap> heap;

int main()
{
    int maxCur, maxFin, n, i;
    FILE *fin = fopen("heavymetal.in", "r");
    fscanf(fin, "%d", &n);
    for (i = 0; i < n; i++)
        fscanf(fin, "%d%d", &shows[i].lo, &shows[i].hi);
    sort(shows, shows + n, cmpSort);
    fclose(fin);

    maxCur = maxFin = 0;
    for (i = 0; i < n; i++)
    {
        while (!heap.empty() && shows[i].lo >= heap.top().hi)
        {
            maxCur = max(maxCur, heap.top().maxlen);
            heap.pop();
        }
        heap.push({shows[i].hi, maxCur + shows[i].hi - shows[i].lo});
        maxFin = max(maxFin,  maxCur + shows[i].hi - shows[i].lo);
    }

    FILE *fout = fopen("heavymetal.out", "w");
    fprintf(fout, "%d", maxFin);
    fclose(fout);
    return 0;
}