Cod sursa(job #2545717)

Utilizator DordeDorde Matei Dorde Data 13 februarie 2020 14:05:19
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
int const NM = 1e5 + 1;
pair <int , int> v [NM] , sol [NM];
bool crt (pair <int , int> a , pair <int , int> b){
    if (a . first == b . first)
        return a . second < b . second;
    return a . first < b . first;
}
int main()
{
    int n;
    f >> n;
    for(int i = 1 ; i <= n ; ++ i)
        f >> v [i] . first >> v [i] . second;
    sort (v + 1 , v + 1 + n , crt);
    pair <int , int > e = v [1];
    int j = 1 , k = 1 , ans = 0;
    sol [1] = e;
    for(int i = 2 ; i <= n ; ++ i){
        if (e . first == v [i] . first)
            sol [k] . second = max (v [i] . second , e . second);
        else
            if (e . second == v [i] . first)
                sol [k] . second = v [i] . second;
            else
                if (v [i] . first > e . second)
                    sol [++ k] = v [i];
        e = sol [k];
    }
    sort (sol + 1 , sol + 1 + k , crt);
    for(int i = 1 ; i <= k ; ++ i)
        ans += sol [i] . second - sol [i] . first;
    g << ans;
    return 0;
}