Cod sursa(job #466955)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 28 iunie 2010 00:08:55
Problema Cadrane Scor Ascuns
Compilator cpp Status done
Runda Marime 3.57 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;
    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++) {
            aintAdd(k, k, up/* - down*/);
        }
        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, j));
    }
    printf("\n");
#endif
    int BST = aintMin[1];
    for (l = 0; l < N; ) {
        vector<int> pozAdd, pozSub;
        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
            int poz = -1, step = (MAXT >> 2);
            for (; step; step >>= 1) {
                if (poz + step < N && Y[oY[poz + step]] < Y[oX[i]]) {
                    poz += step;
                }
            }
            aintAdd(0, poz, 1);
            pozAdd.push_back(poz);
            for (step = (MAXT >> 2); step; step >>= 1) {
                if (poz + step < N && Y[oY[poz + step]] <= Y[oX[i]]) {
                    poz += step;
                }
            }
            /* aintAdd(poz + 1, N - 1, -1); */
            pozSub.push_back(poz + 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, j));
        }
        printf("\n");
#endif
        BST = max(BST, aintMin[1]);

        for (int i = l; i <= r; i++) {
#ifdef DEBUG
            printf("add %d %d %d\n", 0, pozAdd[i - l], 1);
            printf("sub %d %d %d\n", pozSub[i - l], N - 1, 1);
#endif
            /* aintAdd(0, pozAdd[i - l], 1); */
            aintAdd(pozSub[i - l], 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, j));
    }
    printf("\n");
#endif
    BST = max(BST, aintMin[1]);

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

    return 0;
}