Cod sursa(job #2461631)

Utilizator IonAdrianIon Adrian IonAdrian Data 25 septembrie 2019 21:47:28
Problema Cadrane Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
const int N = 1e5;

vector <int> v[1 + N];
struct Point {
    int x;
    int y;
};
Point a[1 + N];
int seg[1 + 4 * N], lazy[1 + 4 * N];
int nx, ny;
int n;
void norm ()
{
    map <int, int> mp;
    for (int i = 1; i <= n; i++)
        mp[a[i].x] = 0;
    nx = 0;
    for (auto &x : mp)
        x.second = ++nx;
    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] = 0;
    ny = 0;
    for (auto &x : mp)
        x.second = ++ny;
    for (int i = 1; i <= n; i++)
        a[i].y = mp[a[i].y];

    for (int i = 1; i <= n; i++)
        v[a[i].x].pb (a[i].y);
}

void push (int node)
{
    lazy[node * 2] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
    lazy[node] = 0;
}

void update (int node, int l, int r, int nl, int nr, int val)
{
    if (nl <= l && r <= nr)
    {
        lazy[node] += val;
        return;
    }

    push (node);

    int mid = (l + r) / 2;
    if (mid < nr)
        update (node * 2 + 1, mid + 1, r, nl, nr, val);
    if (mid >= nl)
        update (node * 2, l, mid, nl, nr, val);

    seg[node] = min (seg[node * 2] + lazy[node * 2], seg[node * 2 + 1] + lazy[node * 2 + 1]);
}

void update (int l, int r, int val)
{
    update (1, 1, ny, l, r, val);
}

int best ()
{
    return seg[1] + lazy[1];
}

int main()
{
    freopen ("cadrane.in", "r", stdin);
    freopen ("cadrane.out", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;

    norm ();

    for (int i = 1; i <= n; i++)
        update (1, a[i].y, 1);

    int ans = 0;
    for (int i = 1; i <= nx; i++)
    {
        for (auto it : v[i])
            update (it, ny, 1);
        for (auto it : v[i - 1])
            update (1, it, -1);
        ans = max (ans, best ());
    }

    cout << ans << "\n";
    return 0;
}