Cod sursa(job #1876819)

Utilizator RobybrasovRobert Hangu Robybrasov Data 12 februarie 2017 17:40:42
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 666013
#define N 100000
#define INF 0x3f3f3f3f
#define iter vector<pair<int, int> >::iterator 

using namespace std;

class hash_table {
    vector<pair<int, int> > L[MOD];

    public: int &operator[](int x) {
        int v = x % MOD;
        iter it;
        for (it = L[v].begin(); it != L[v].end() && it -> first != v; ++it);
        if (it == L[v].end()) {
            L[v].push_back(make_pair(x, -INF));
            return L[v][L[v].size() - 1].second;
        }
        return it -> second;
    }
};

hash_table H;
int A[N], B[N], I[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 = 0; i < n; ++i) {
        int a, b;
        fin >> a >> b;
        A[i] = a;
        B[i] = b;
        I[i] = i;
    }

    sort(I, I + n, comp);

    H[B[I[0]]] = B[I[0]] - A[I[0]];
    for (int i = 1; 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;
        }
        if (B[I[val]] <= A[I[i]])
            H[B[I[i]]] = max(H[B[I[i]]], H[B[I[val]]] + B[I[i]] - A[I[i]]);
        else 
            H[B[I[i]]] = B[I[i]] - A[I[i]];
    }
    fout << H[B[I[n - 1]]] << "\n";

    return 0;
}