Cod sursa(job #608200)

Utilizator SpiderManSimoiu Robert SpiderMan Data 15 august 2011 17:11:12
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
# include <algorithm>
# include <cstdio>
using namespace std;

# define x first
# define y second

const char *FIN = "cadrane.in", *FOU = "cadrane.out";
const int MAX = 100005;

pair <int, int> V[MAX], ai[MAX << 2];
int N, M, A[MAX];

void update (int nod, int st, int dr, int poz, int val) {
    if (st == dr) {
        ai[nod].y = (ai[nod].x += val);
        return ;
    }
    int mij = st + dr >> 1;
    if (poz <= mij) update (nod << 1, st, mij, poz, val);
    else            update (nod << 1 | 1, mij + 1, dr, poz, val);
    ai[nod].x = ai[nod << 1].x + ai[nod << 1 | 1].x;
    ai[nod].y = min (ai[nod << 1].y, ai[nod << 1].x + ai[nod << 1 | 1].y);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf ("%d %d", &V[i].x, &V[i].y);
        A[++A[0]] = V[i].y;
    }
    sort (V + 1, V + N + 1);
    sort (A + 1, A + A[0] + 1);
    const int lim = A[0]; A[0] = 1;
    for (int i = 2; i <= lim; ++i) {
        if (A[A[0]] == A[i]) continue;
        A[++A[0]] = A[i];
    }
    for (int i = 1; i <= N; ++i)
        update (1, 1, N, (V[i].y = lower_bound (A + 1, A + A[0] + 1, V[i].y) - A) + 1, -1);
    int sol = 0;
    for (int i = 1, j = 1, cnt = N; i <= N; i = j) {
        for (; j <= N && V[i].x == V[j].x; update (1, 1, N, V[j].y + 1, 1), ++j);
        sol = max (sol, cnt + ai[1].y), cnt -= j - i;
        for (int k = i; k < j; ++k)
            update (1, 1, N, V[k].y, 1);
    }
    fprintf (fopen (FOU, "w"), "%d", sol);
}