Cod sursa(job #1876863)

Utilizator RobybrasovRobert Hangu Robybrasov Data 12 februarie 2017 18:19:13
Problema Heavy metal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define N 100000
#define INF 0x3f3f3f3f
#define iter vector<pair<int, int> >::iterator 

using namespace std;

int A[N], B[N], I[N], H[N];

bool comp(int a, int b) {
    return B[a] < B[b];
}

int main() {
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        int a, b;
        fin >> a >> b;
        A[i] = a;
        B[i] = b;
        I[i] = i;
    }

    sort(I + 1, I + n + 1, comp);

    H[I[1]] = B[I[1]] - A[I[1]];
    for (int i = 2; i <= n; ++i) {
        // Binary-search for the event ending with A[i]
        int step, val;
        for (step = 1; step < i; step <<= 1);
        for (val = 0; step; step >>= 1) {
            int v = val + step;
            if (v < i && B[I[v]] <= A[I[i]])
                val = v;
        }
        H[I[i]] = max(H[I[i - 1]], H[I[val]] + B[I[i]] - A[I[i]]);
    }
    fout << H[I[n]] << "\n";

    return 0;
}