Cod sursa(job #1559071)

Utilizator akaprosAna Kapros akapros Data 29 decembrie 2015 23:58:51
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
struct coord
{
    int x;
    int y;
    int z;
} v[maxN];
int sol, n, p[maxN], app[maxN], arb[maxN * 4], add[maxN * 4];
int cmpy(const int a, const int b)
{
    return v[a].y < v[b].y;
}
int cmpx(const coord a, const coord b)
{
    return a.x < b.x;
}
void read()
{
    int i;
    freopen("cadrane.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &v[i].x, &v[i].y);
        p[i] = i;
    }
}
void norm()
{
    int i, act = 0;
    sort(p + 1, p + n + 1, cmpy);
    for (i = 1; i <= n; ++ i)
    {
        ++ act; ++app[act];
        for (; i < n && v[p[i]].y == v[p[i + 1]].y; ++ i)
        {
            v[p[i]].y = act;
            ++ app[act];
        }
        v[p[i]].y = act;
    }
    sort(v + 1, v + n + 1, cmpx);
}
void update(int node, int l, int r, int x, int y, int val)
{
    int Val;
    if (l > r || r < x || l > y)
        return ;
    if (x <= l && r <= y)
    {
        arb[node] += val;
        add[node] += val * (r - l + 1);
        return ;
    }
    int lson = node * 2, rson = lson + 1, mid = (l + r) >> 1;
    if (add[node] - add[lson] - add[rson])
    {
        Val = (add[node] - add[lson] - add[rson]) / (r - l + 1);
        add[lson] += Val * (mid - l + 1);
        add[rson] += Val * (r - mid);
        arb[lson] += Val;
        arb[rson] += Val;
    }
    update(lson, l, mid, x, y, val);
    update(rson, mid + 1, r, x, y, val);
    arb[node] = min(arb[lson], arb[rson]);
    add[node] = add[lson] + add[rson];
}
void solve()
{
    int i;
    norm();
    for (i = 1; i <= n; ++ i)
    {
        app[i] += app[i - 1];
        update(1, 1, n, i, i, n - app[i - 1]);
    }
    int act = 1;
    for (i = 1; i <= n; ++ i)
    {
        for (; v[act].x < v[i].x; ++ act)
            update(1, 1, n, 1, v[act].y, -1);
        for (; i < n && v[i].x == v[i + 1].x; ++ i)
            update(1, 1, n, v[i].y, n, 1);
         update(1, 1, n, v[i].y, n, 1);
         sol = max(sol, arb[1]);
    }
}
void write()
{
    freopen("cadrane.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}