Cod sursa(job #1759005)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 septembrie 2016 12:50:57
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("cadrane.in");
ofstream cout("cadrane.out");

const int MAXN = 100000;

struct Point {
    int x, y;
    int index;
};

Point v[1 + MAXN];
int value[1 + MAXN + 1], limit;

bool CompareX(const Point &a, const Point &b) {
    return a.x < b.x;
};

bool CompareY(const Point &a, const Point &b) {
    return a.y < b.y;
};

void Normalize(int n) {
    sort(v + 1, v + n + 1, CompareY);
    value[v[1].index] = 1;
    for (int i = 2; i <= n; i++) {
        value[v[i].index] = value[v[i - 1].index];
        if (v[i].y != v[i - 1].y)
            value[v[i].index]++;
    }
    limit = value[v[n].index];
}

int tree[1 + 4 * MAXN], lazy[1 + 4 * MAXN];

void Update(int node, int left, int right, int leftIndex, int rightIndex, int add) {
    if (right < leftIndex || rightIndex < left)
        return;
    if (leftIndex <= left && right <= rightIndex) {
        lazy[node] += add;
        return;
    }
    int middle = (left + right) / 2;
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    lazy[node] = 0;
    if (leftIndex <= middle)
        Update(2 * node, left, middle, leftIndex, rightIndex, add);
    if (middle + 1 <= rightIndex)
        Update(2 * node + 1, middle + 1, right, leftIndex, rightIndex, add);
    tree[node] = min(tree[2 * node] + lazy[2 * node], tree[2 * node + 1] + lazy[2 * node + 1]);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
        v[i].index = i;
    }
    Normalize(n);
    sort(v + 1, v + n + 1, CompareX);
    for (int i = 1; i <= n; i++)
        Update(1, 1, limit, 1, value[v[i].index], 1);
    int j = 1;
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        Update(1, 1, limit, value[v[i].index], limit, 1);
        if (v[i].x != v[i + 1].x) {
            answer = max(answer, tree[1] + lazy[1]);
            while (j <= i) {
                Update(1, 1, limit, 1, value[v[j].index], -1);
                j++;
            }
        }
    }
    cout << answer << "\n";
    return 0;
}