Cod sursa(job #2497988)

Utilizator Simi_bogdanSimion Bogdan Dumitru Simi_bogdan Data 23 noiembrie 2019 13:12:02
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int dp[100001];
int  suma=0;
int n;
int x=1;
struct timp
{
    int st,f;


}lista[100001];
void read()
{
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>lista[i].st>>lista[i].f;
    }
}
bool comparare(timp a ,timp b)
{
    return (a.f<b.f || a.st==b.st);
}
void sortare()
{
    sort(lista+1,lista+n+1,comparare);

}
void solve(int &i)
{
    int j=i;
    while(lista[j].st<dp[x-1])
        j++;
    dp[x]=lista[j].f;
    suma=dp[x]-lista[j].st+suma;
    i=j;
}
int main()
{
    read();
    sortare();
    dp[x]=lista[1].f;
    suma=lista[1].f-1;
    x++;
    for(int i=2;i<=n;i++ )
    {

        solve(i);
    }
    out<<suma-1;
}
/*
1 4
2 5
5 12
5 6
6 8
8 11
11 14*/