Cod sursa(job #1695198)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 26 aprilie 2016 18:47:52
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int NMAX = 100505;
const int LMAX = (1 << 18);
int N, M;

struct pt {
    int x, y;
};
pt A[NMAX];
vector<int> sortedX, sortedY, cnt;
vector<int> pointAtX[NMAX], pointAtY[NMAX];

struct node {
    int minV;
    int updateV;

    int get() {
        return minV + updateV;
    }
};
node G[LMAX];

inline void updateFromChildren(int node) {
    G[node].minV = min(G[node * 2].get(), G[node * 2 + 1].get());
}

inline void lazyExpand(int node) {
    G[node].minV += G[node].updateV;
    G[node * 2].updateV += G[node].updateV;
    G[node * 2 + 1].updateV += G[node].updateV;
    G[node].updateV = 0;
}

inline void sortAndUnique(vector<int>& H) {
    sort(H.begin(), H.end());
    H.resize(unique(H.begin(), H.end()) - H.begin());
}

void read() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d%d", &A[i].x, &A[i].y);
        sortedX.push_back(A[i].x);
        sortedY.push_back(A[i].y);
    }

    sortAndUnique(sortedX);
    sortAndUnique(sortedY);
    reverse(sortedY.begin(), sortedY.end());
    for (int i = 1; i <= N ;i++) {
        A[i].x = lower_bound(sortedX.begin(), sortedX.end(),
            A[i].x) - sortedX.begin();
        A[i].y = lower_bound(sortedY.begin(), sortedY.end(),
            A[i].y, greater<int>()) - sortedY.begin();
    }
}

void cstr(int left, int right, int node, vector<int>& cnt) {
    if (left == right) {
        G[node].minV = cnt[left];
        return ;
    }

    int mid = (left + right) >> 1;
    cstr(left, mid, node * 2, cnt);
    cstr(mid + 1, right, node * 2 + 1, cnt);
    G[node].minV = min(G[node * 2].minV, G[node * 2 + 1].minV);
}

void prepare() {
    for (int i = 1; i <= N; i++) {
        pointAtX[A[i].x].push_back(A[i].y);
        pointAtY[A[i].y].push_back(A[i].x);
    }
    // cnt[i] = score if x = smallest_x and y = i
    int smallestX = 0;
    int currV = pointAtX[smallestX].size();

    M = sortedY.size();
    cnt.assign(M, 0);
    for (int i = 0; i < M; i++) {
        for (auto& x: pointAtY[i]) {
            if (x != smallestX) {
                currV++;
            }
        }
        cnt[i] = currV;
    }
    cstr(0, M - 1, 1, cnt);
}

void update(int left, int right, int node, int l, int r, int v) {
    if (right < l || r < left) {
        return ;
    }
    if (l <= left && right <= r) {
        G[node].updateV += v;
        return ;
    }
    lazyExpand(node);

    int mid = (left + right) >> 1;
    update(left, mid, node * 2, l, r, v);
    update(mid + 1, right, node * 2 + 1, l, r, v);
    
    updateFromChildren(node);
}

void solve() {
    int result = G[1].get();
    for (size_t i = 1; i < sortedX.size(); i++) {
        for (auto& y: pointAtX[i - 1]) {
            update(0, M - 1, 1, y + 1, M - 1, -1);
        }
        for (auto& y: pointAtX[i]) {
            update(0, M - 1, 1, 0, y - 1, 1);
        }

        result = max(result, G[1].get());
    }
    printf("%d\n", result);
}

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

    read();
    prepare();
    solve();
    return 0;
}