Cod sursa(job #2632187)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 2 iulie 2020 14:35:30
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <algorithm>
#include <map>
#define x first
#define y second

using namespace std;

typedef pair <int, int> PI;
constexpr int NMAX = 1e5 + 5;

ifstream f ("cadrane.in");
ofstream g ("cadrane.out");

int N, Max_X, Max_Y;
PI a[NMAX];

int arb[4 * NMAX], lazy[4 * NMAX];

void Propag (int nod, int a, int b) {
    if (a == b) return;
    if (lazy[ nod ] == 0) return;

    lazy[2 * nod] += lazy[ nod ];
    lazy[2 * nod + 1] += lazy[ nod ];
    arb[2 * nod] += lazy[ nod ];
    arb[2 * nod + 1] += lazy[ nod ];

    lazy[ nod ] = 0;
}

void Update (int nod, int a, int b, int ua, int ub, int val) {
    Propag(nod, a, b);
    if (ua <= a && b <= ub) {
        arb[ nod ] += val;
        lazy[ nod ] += val;
        return;
    }

    int mij = (a + b) / 2;
    if (ua <= mij) Update(2 * nod, a, mij, ua, ub, val);
    if (mij < ub) Update(2 * nod + 1, mij + 1, b, ua, ub, val);

    arb[ nod ] = min(arb[ 2 * nod], arb[ 2 * nod + 1]);
}

void Read () {
    f >> N;
    for (int i = 1; i <= N; ++ i ) {
        f >> a[ i ].x >> a[ i ].y;
    }
}

void NormalizareAndSortare () {
    map <int, int> mp;
    for (int i = 1; i <= N; ++ i ) {
        mp[a[ i ].x] = 1;
    }
    for (auto &it : mp) {
        it.second = ++Max_X;
    }
    for (int i = 1; i <= N; ++ i ) {
        a[ i ].x = mp[a[ i ].x];
    }
    mp.clear();
    for (int i = 1; i <= N; ++ i ) {
        mp[a[ i ].y] = 1;
    }
    for (auto &it : mp) {
        it.second = ++Max_Y;
    }
    for (int i = 1; i <= N; ++ i ) {
        a[ i ].y = mp[a[ i ].y];
    }

    sort(a+1, a+N+1);
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        Update(1, 1, Max_Y, 1, a[ i ].y, 1);
    }
    int ind = 1;
    int ans = 0;

    for (int i = 1; i <= Max_X; ++ i ) {
        int aux = ind;
        while (aux <= N && a[ aux ].x == i) {
            Update(1, 1, Max_Y, a[ aux ].y, Max_Y, 1);
            ++ aux;
        }

        ans = max(ans, arb[1]);
        while (ind <= N && a[ ind ].x == i) {
            Update(1, 1, Max_Y, 1, a[ ind ].y, -1);
            ++ ind;
        }
    }

    g << ans << '\n';
}

int main()
{
    Read ();
    NormalizareAndSortare ();
    Solve ();

    return 0;
}