Cod sursa(job #2729705)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 25 martie 2021 09:52:16
Problema Heavy metal Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
#define dim 100002
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
long long    nr[2*dim],dp[2*dim];
unordered_map<long long   ,long long   > asoc;


struct el
{
    long long    a,b;
}v[dim];


inline bool cmp (const el &a1,const el &a2)
{
    if (a1.a==a2.a)
        return a1.b<a2.b;
    return a1.a<a2.a;
}

int main()
{
    long long  n,i,ct=1,j=1;
    fin>>n;
    for (i=1;i<=n;i++)
    {
        fin>>v[i].a>>v[i].b;
        v[i].a++;
        nr[2*i]=v[i].b;
        nr[2*i-1]=v[i].a;
    }
    sort(nr+1,nr+2*n+1);
    sort(v+1,v+n+1,cmp);
    for (i=1;i<=2*n;i++)
        if (nr[i]!=nr[i-1])
            asoc[nr[i]]=ct++;
    for (i=1;i<ct;i++)
    {
        dp[i]=max(dp[i],dp[i-1]);
        while (asoc[v[j].a]==i && j<=n)
        {
            dp[asoc[v[j].b]]=dp[asoc[v[j].a]]+v[j].b-v[j].a+1;
            ++j;
        }
    }
    fout<<dp[ct-1]<<'\n';
}