Cod sursa(job #2970700)

Utilizator YosifIosif Andrei Stefan Yosif Data 25 ianuarie 2023 19:04:18
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<bits/stdc++.h>
using namespace std;

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

pair <int, int> v[100001];
map <int, int> M;
map <int, int>::iterator it;
int n;

bool comp(pair <int, int> a, pair <int, int> b)
{
    if (a.second < b.second)
        return true;
    else if (a.second == b.second)
        return a.first < b.first;

    return false;
}

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;

    sort(v + 1, v + n + 1, comp);

    int i = 1;
    
    while (i <= n)
    {
        int c = v[i].second;
        int maxi = 0;

        while (i <= n && v[i].second == c)
        {
            it = M.lower_bound(v[i].first);

            if (M.size() == 0 || it == M.begin())
                maxi = max(maxi, v[i].second - v[i].first);
            else if (it == M.end() || it->first != v[i].first)
                it--, maxi = max(maxi, it->second + v[i].second - v[i].first);
            else
                maxi = max(maxi, it->second + v[i].second - v[i].first);
            i++;
        }

        it = M.end();
        if (M.size())
        {
            it--;
            M[c] = max(maxi, it->second);
        }
        else
            M[c] = maxi;
    }

    it = M.end();
    it--;
    fout << it->second;

    return 0;
}