Cod sursa(job #1851475)

Utilizator preda.andreiPreda Andrei preda.andrei Data 19 ianuarie 2017 19:42:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

void Normalizeaza(vector<int> &v)
{
    sort(v.begin(), v.end());
    vector<int> unic;

    for (unsigned i = 0; i < v.size(); ++i) {
        if (i == 0 || v[i] != v[i - 1]) {
            unic.push_back(v[i]);
        }
    }
    v = unic;
}

int Rang(const vector<int> &v, int x)
{
    int st = 0, dr = v.size() - 1;
    while (st <= dr) {
        int mij = st + (dr - st) / 2;
        if (v[mij] == x) {
            return mij + 1;
        } else if (v[mij] > x) {
            dr = mij - 1;
        } else {
            st = mij + 1;
        }
    }
    return -1;
}

int PutereZerouri(int x)
{
    return (x ^ (x - 1)) & x;
}

int GasesteMax(const vector<int> &aib, unsigned poz)
{
    int rez = 0;
    while (poz > 0) {
        rez = max(rez, aib[poz]);
        poz -= PutereZerouri(poz);
    }
    return rez;
}

void Actualizeaza(vector<int> &aib, unsigned poz, int val)
{
    while (poz < aib.size()) {
        aib[poz] = max(aib[poz], val);
        poz += PutereZerouri(poz);
    }
}

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

    int n;
    fin >> n;

    vector<int> ranguri;
    vector<pair<int, int>> intervale(n);

    for (int i = 0; i < n; ++i) {
        int x, y;
        fin >> x >> y;
        intervale[i] = {x, y};
        ranguri.push_back(x);
        ranguri.push_back(y);
    }

    Normalizeaza(ranguri);

    auto cmpInter = [] (const pair<int, int> &a, const pair<int, int> &b) -> bool
    {
        return a.second < b.second;
    };
    sort(intervale.begin(), intervale.end(), cmpInter);

    vector<int> aib(ranguri.size() + 1);
    int rez = 0;

    for (const auto &inter : intervale) {
        int rang_x = Rang(ranguri, inter.first);
        int rang_y = Rang(ranguri, inter.second);
        int len = inter.second - inter.first;

        int len_total = GasesteMax(aib, rang_x) + len;
        rez = max(rez, len_total);
        Actualizeaza(aib, rang_y, len_total);
    }

    fout << rez << "\n";
    return 0;
}