Cod sursa(job #2276292)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 4 noiembrie 2018 15:44:15
Problema Heavy metal Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int aib[200002];
map<int, int>sorted;
int n;
struct intervale
{
    int a, b;
};
intervale v[100002];
bool cmp(intervale a, intervale b)
{
    return a.a < b.a;
}
void update(int pos, int val)
{
    for(int i = pos; i <= sorted.size(); i += (i & (-i)))
        aib[i] = max(aib[i], val);
}
int compute(int pos)
{
    int sol = 0;
    for(int i = pos; i; i -= (i & (-i)))
        sol = max(sol, aib[i]);
    return sol;
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i].a >> v[i].b, sorted[v[i].a] = 1, sorted[v[i].b] = 1;
    sort(v+1, v+n+1, cmp);
    map<int, int> ::iterator it;
    int ax = 0;
    for(it = sorted.begin(); it != sorted.end(); ++it)
    {
        ++ax;
        it->second = ax;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        int val = compute(sorted[v[i].a]) + (v[i].b - v[i].a);
        ans = max(ans, val);
        update(sorted[v[i].b], val);
    }
    g << ans << '\n';
    return 0;
}