Cod sursa(job #2912705)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 10 iulie 2022 03:49:24
Problema Cadrane Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>

std::ifstream fin("cadrane.in");
std::ofstream fout("cadrane.out");

int const nmax = 1e5;
std::vector <int> bfNormX;
std::vector <int> bfNormY;
std::map <int, int> normX;
std::map <int, int> normY;
std::vector <std::pair <int, int>> bfNormPuncte;
std::vector <std::pair <int, int>> puncte;

void normalize(int n) {
    std::sort(bfNormX.begin(), bfNormX.end());
    int normalized = 1;
    for (int i = 0; i < n; i++) {
        if (i > 0 && bfNormX[i - 1] == bfNormX[i]) continue;
        normX[bfNormX[i]] = normalized++;
    }
    std::sort(bfNormY.begin(), bfNormY.end());
    normalized = 1;
    for (int i = 0; i < n; i++) {
        if (i > 0 && bfNormY[i - 1] == bfNormY[i]) continue;
        normY[bfNormY[i]] = normalized++;
    }
    for (int i = 0; i < n; i++) {
        puncte.push_back({normX[bfNormPuncte[i].first],
                          normY[bfNormPuncte[i].second]});
    }
}

namespace AINT {
    int const offset = (1 << 17);
    int const INF = 1e8;
    int aint[2 * offset + 5];
    int lazy[2 * offset + 5];

    void init_helper (int nod, int l, int r, int n) {
        if (n < l)
            aint[nod] = INF;
        if (l <= n)
            aint[nod] = 0;
        if (l == r) return;
        int med = (l + r) >> 1;
        init_helper (nod * 2, l, med, n);
        init_helper (nod * 2 + 1, med + 1, r, n);
    }

    void init (int n) {
        init_helper(1, 1, offset, n);
    }

    void push_lazy (int nod) {
        aint[nod] += lazy[nod];
        if (nod < offset) {
            lazy[nod * 2] += lazy[nod];
            lazy[nod * 2 + 1] += lazy[nod];
        }
        lazy[nod] = 0;
    }

    void update_helper (int nod, int l, int r, int st, int dr, int val) {
        push_lazy(nod);
        if (dr < l || r < st)
            return;
        if (st <= l && r <= dr) {
            lazy[nod] += val;
            push_lazy(nod);
            return;
        }
        int med = (l + r) >> 1;
        update_helper((nod << 1), l, med, st, dr, val);
        update_helper((nod << 1) + 1, med + 1, r, st, dr, val);
        aint[nod] = std::min(aint[(nod << 1)], aint[(nod << 1) + 1]);
    }

    void update (int st, int dr, int val) {
        update_helper(1, 1, offset, st, dr, val);
    }

    int query () {
        push_lazy(1);
        return aint[1];
    }

}

int main() {
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;
        bfNormX.push_back(x);
        bfNormY.push_back(y);
        bfNormPuncte.push_back({x, y});
    }
    normalize(n);
    AINT::init(n);
    std::sort(puncte.begin(), puncte.end());
    for (int i = 0; i < n; i++)
        AINT::update(1, puncte[i].second, 1);
    int ans = -1e9;
    for (int i = 0; i < n; i++) {
        AINT::update(puncte[i].second + 1, n, 1);
        ans = std::max(ans, AINT::query());
        AINT::update(1, puncte[i].second - 1, -1);
    }
    fout << ans;
    return 0;
}