Cod sursa(job #467710)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 29 iunie 2010 23:42:32
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100000
#define MAXT 262144

int N, X[MAXN], Y[MAXN], oX[MAXN], oY[MAXN];
int aintVal[MAXT], aintMin[MAXT];

inline int cmpX(int a, int b) {
    return X[a] < X[b];
}

inline int cmpY(int a, int b) {
    return Y[a] < Y[b];
}

#define AINTCOMMON int lc = (n << 1), rc = (lc + 1), m = (l + r) >> 1

int UL, UR, UV;
inline void update(int n, int l, int r) {
    if (UL <= l && r <= UR) {
        aintVal[n] += UV;
        aintMin[n] += UV;
        return;
    }

    AINTCOMMON;
    if (UL <= m) {
        update(lc, l, m);
    }
    if (UR > m) {
        update(rc, m + 1, r);
    }
    aintMin[n] = min(aintMin[lc], aintMin[rc]) + aintVal[n];
}

inline void aintAdd(int l, int r, int val) {
    if (l > r) {
        return;
    }

    UL = l; UR = r; UV = val;
    update(1, 0, N - 1);
}

inline int aintQuery(int n, int l, int r, int p) {
    if (l == r) {
        return aintVal[n];
    }

    AINTCOMMON;
    if (p <= m) {
        return aintQuery(lc, l, m, p) + aintVal[n];
    } else {
        return aintQuery(rc, m + 1, r, p) + aintVal[n];
    }
}

int main() {
    freopen("cadrane.in", "rt", stdin);
#ifndef DEBUG
    freopen("cadrane.out", "wt", stdout);
#endif

    assert(scanf("%d", &N) == 1);
    assert(1 <= N && N <= MAXN);
    for (int i = 0; i < N; i++) {
        assert(scanf("%d %d", X + i, Y + i) == 2);
        X[i] = -X[i];
        oX[i] = oY[i] = i;
    }

    sort(oX, oX + N, cmpX);
    sort(oY, oY + N, cmpY);

    int l, r, cnt = 0;
    for (l = 0; l < N; ) {
        for (r = l; r < N && Y[oY[l]] == Y[oY[r + 1]]; r++);
        int up = r + 1/* , down = N - l */;
        for (int k = l; k <= r; k++) {
            Y[oY[k]] = cnt;
        }
        aintAdd(cnt, cnt, up/* - down*/);
        l = r + 1; cnt += 1;
    }
    for (; cnt < N; cnt++) {
        aintAdd(cnt, cnt, 0x3f3f3f3f);
    }

#ifdef DEBUG
    for (int j = 0; j < N; j++) {
        printf("%d - %d %d - %d\n", oY[j], X[oY[j]], Y[oY[j]],
                aintQuery(1, 0, N - 1, Y[oY[j]]));
    }
    printf("\n");
#endif
    int BST = aintMin[1];
    for (l = 0; l < N; ) {
        for (r = l; r + 1 < N && X[oX[l]] == X[oX[r + 1]]; r++);

        for (int i = l; i <= r; i++) {
#ifdef DEBUG
            printf("\t%d %d\n", X[oX[i]], Y[oX[i]]);
#endif
            aintAdd(0, Y[oX[i]] - 1, 1);
            /* aintAdd(Y[oX[i]] + 1, N - 1, -1); */
        }

#ifdef DEBUG
        for (int j = 0; j < N; j++) {
            printf("%d - %d %d - %d\n", oY[j], X[oY[j]], Y[oY[j]],
                    aintQuery(1, 0, N - 1, Y[oY[j]]));
        }
        printf("\n");
#endif
        BST = max(BST, aintMin[1]);

        for (int i = l; i <= r; i++) {
            /* aintAdd(0, Y[oX[i]] - 1, 1); */
            aintAdd(Y[oX[i]] + 1, N - 1, -1);
        }
        l = r + 1;
    }

#ifdef DEBUG
    for (int j = 0; j < N; j++) {
        printf("%d - %d %d - %d\n", oY[j], X[oY[j]], Y[oY[j]],
                aintQuery(1, 0, N - 1, Y[oY[j]]));
    }
    printf("\n");
#endif
    BST = max(BST, aintMin[1]);

    printf("%d\n", BST);

    return 0;
}