Cod sursa(job #2482662)

Utilizator BogdanRazvanBogdan Razvan BogdanRazvan Data 28 octombrie 2019 18:22:44
Problema Heavy metal Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

const int N = 1000005;

pair < int, int > a[N];

int f[N], dad[N];

void usain_bolt()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
}

int bs(int k, int n)
{
    int sol = -1;
    int st = 1, dr = n, mx = 0, pos = -1;
    while(st <= dr) {
        int mid = (st + dr) >> 1;
        if(k >= a[mid].second) {
            if(sol == -1) sol = mid, pos = a[mid].second;
            else {
                if(a[mid].second > pos) sol = mid;
                pos = max(pos, a[mid].second);
            }
            st = mid + 1;
        }
        else dr = mid - 1;
    }
    return sol;
}

void path(int k, int & ans)
{
    if(dad[k]) path(dad[k], ans);
    ans += a[k].second - a[k].first;
}

int main()
{
    usain_bolt();

    int n;

    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i].first >> a[i].second;

    sort(a + 1, a + 1 + n);

    for(int i = 2; i <= n; ++i) {
        int pos = bs(a[i].first, i);
        if(pos != -1)
            dad[i] = pos;
    }
    int ans = 0;

    for(int i = 1; i <= n; ++i) {
        int cnt = 0;
        path(i, cnt);
        ans = max(ans, cnt);
    }

    fout << ans;
    return 0;
}