Cod sursa(job #821400)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 22 noiembrie 2012 13:04:05
Problema Cadrane Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

const int N = 110000;

int n, x[N], y[N], p[N], vec[N], smin[4 * N], aint[4 * N], cmax, cc, rez, ymax;

bool cmp(int a, int b) {
    return vec[a] < vec[b];
}

void norm(int *x) {
    int i, nr = 0;
    map<int, int> s;

    for(i = 1; i<=n; ++i)
        p[i] = i, vec[i] = x[i];
    sort(p + 1, p + n + 1, cmp);

    for(i = 1; i<=n; ++i) if(i == 1 || vec[p[i]] != vec[p[i - 1]]) {
        p[++nr] = p[i];
        s[vec[p[i]]] = nr;
    }
    cc = nr;
    for(i = 1; i<=n; ++i)
        x[i] = s[x[i]];
}

void update(int nod, int pozx, int pozy, int poz1, int poz2, int val) {
    if(pozx >= poz1 && pozy <= poz2) {
        smin[nod] += val;
        aint[nod] += val;

        return;
    }
    int mid = (pozx + pozy)/2;

    if(mid >= poz1)
        update(2 * nod, pozx, mid, poz1, poz2, val);
    if(mid < poz2)
        update(2 * nod + 1, mid + 1, pozy, poz1, poz2, val);

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

void bal() {
    int i, co, j;

    for(i = 1; i<=n; ++i) {
        p[i] = i, vec[i] = y[i];
		
		update(1, 1, cmax, 1, x[i], 1);
    }

    sort(p + 1, p + n + 1, cmp);

    for(i = 1, j = 1, co = 1; co <= ymax; ++co) {

        while(i <= n && y[p[i]] <= co) {

            if(x[p[i]] != cmax)
                update(1, 1, cmax, x[p[i]] + 1, cmax, 1);

            ++i;
        }

        while(j <= n && y[p[j]] < co) {

            if(x[p[j]] != 1)
                update(1, 1, cmax, 1, x[p[j]] - 1, -1);
            
            ++j;
        }

        rez = max(rez, smin[1]);
    }
}

int main() {
    int i;

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

    scanf("%d", &n);

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

    norm(x);
    cmax = cc;
    norm(y);
	ymax = cc;
	
    bal();

    cout << rez;

    return 0;
}