Cod sursa(job #2617618)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 22 mai 2020 14:25:21
Problema Cadrane Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>
#define maxn 400005

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

struct point{
    int x, y;
}v[maxn];

bool sortX (point a, point b){
    return a.x < b.x;
}
bool sortY (point a, point b){
    return a.y < b.y;
}

int tree[maxn];
void update (int left, int right, int node, int l, int r, int val){
    if (left > r or right < l or left > right)
        return;

    if (l <= left and right <= r){
        tree[node] += val;
        if (left == right)
            return;
    }

    int mid = (left + right) / 2;
    update (left, mid, 2*node+1, l, r, val);
    update (mid+1, right, 2*node+2, l, r, val);

    tree[node] = std::min (tree[2*node+1], tree[2*node+2]);
}

int main()
{
    int n, i, j, mx, my, crt, min=0;
    fin >> n;
    for (i=0; i<n; i++)
        fin >> v[i].y >> v[i].x;

    std::sort (v, v+n, sortX);
    for (i=0, crt=0; i<n; i++){
        if (v[i].x == v[i+1].x and i != n-1){
            v[i].x = crt;
            continue;
        }
        v[i].x = crt;
        crt ++;
    }
    mx = crt - 1;

    std::sort (v, v+n, sortY);
    for (i=0, crt=0; i<n; i++){
        if (v[i].y == v[i+1].y and i != n -1){
            v[i].y = crt;
            continue;
        }
        v[i].y = crt;
        crt ++;
    }
    my = crt - 1;

    //for (i=0; i<n; i++)
    //   fout << v[i].x << ' ' << v[i].y << '\n';

    for (i=0; i<n; i++)
        update (0, mx, 0, 0, v[i].x, 1);


    for (int y=0, i=0; y<=my; y++){
        for (j=i; j < n and v[j].y == y; j++)
            update (0, mx, 0, v[j].x, mx, 1);

        min = std::max (min, tree[0]);

        for (j=i; j < n and v[j].y == y; j++){
            update (0, mx, 0, 0, mx, -1);
            update (0, mx, 0, v[j].x, v[j].x, -1);
            update (0, mx, 0, v[j].x, mx, 1);
        }
        i = j;
    }

    fout << min << '\n';

    return 0;
}