Cod sursa(job #2299418)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 9 decembrie 2018 15:27:02
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

const int MAX = 1e5 + 5;

struct interval
{
    int x, y, z;
};
interval r[MAX];

int n, t, valpas;
int v[2 * MAX], p[2 * MAX], dp[2 * MAX];

inline bool cmp(interval &a, interval &b)
{
    return a.y < b.y;
}

inline int BS(int x)
{
    int r = 0;

    for(int pas = valpas; pas; pas >>= 1)
        if(r + pas <= t && v[r + pas] <= x)
            r += pas;

    if(v[r] == x)
        return r;
    return 0;
}

void Read_Init()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        f >> r[i].x >> r[i].y;
        r[i].z = r[i].y - r[i].x;
        v[++t] = r[i].x;
        v[++t] = r[i].y;
    }
    sort(v + 1, v + t + 1);

    for(int i = 1; i <= t; ++i)
        if(v[i] != v[i - 1])
            p[i] = p[i - 1] + 1;
        else
            p[i] = p[i - 1];

    for(valpas = 1; valpas <= t; valpas <<= 1);
    for(int i = 1; i <= n; ++i)
    {
        r[i].x = p[BS(r[i].x)];
        r[i].y = p[BS(r[i].y)];
    }

    sort(r + 1, r + n + 1, cmp);


}

void DP()
{
    int j = 1;

    for(int i = 1; i <= t; ++i)
    {
        dp[i] = max(dp[i], dp[i - 1]);
        while(j <= n && r[j].y < i)
            ++j;
        while(j <= n && r[j].y == i)
        {
            dp[i] = max(dp[i], dp[r[j].x] + r[j].z);
            ++j;
        }
    }

    g << dp[t] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    Read_Init();
    DP();
    return 0;
}