Cod sursa(job #1559042)

Utilizator akaprosAna Kapros akapros Data 29 decembrie 2015 22:40:24
Problema Cadrane Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
struct coord
{
    int x;
    int y;
    int z;
} v[maxN], vx[maxN], vy[maxN];
int n, sol, arb[maxN * 4], mval[maxN * 4];
int cmp(const coord a, const coord b)
{
    if (a.x == b.x)
        return a.z < b.z;
    return a.x < b.x;
}
int cmpx(const coord a, const coord b)
{
    if (a.z == b.z)
        return a. x < b.x;
    return a.z < b.z;
}
int Cmp(const coord a, const coord b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
void read()
{
    int i, x, y;
    freopen("cadrane.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d %d", &v[i].x, &v[i].y);
    sort(v + 1, v + n + 1,  Cmp);
    for (i = 1; i <= n; ++ i)
    {
        x = v[i].x;
        y = v[i].y;
        vy[i].x = y;
        vy[i].y = i;
        vy[i].z = x;
    }
    sort(vy+ 1, vy + n+ 1, cmp);
    int j = 1;
    for (i = 1; i <= n; ++ i)
    {
        while (vy[j + 1].x == vy[i].x && j < n)
            ++ j;
        v[vy[i].y].y = j;
    }
    sort(vy+ 1, vy + n+ 1, cmpx);
    j = 1;
    for (i = 1; i <= n; ++ i)
    {
        while (vy[j + 1].z == vy[i].z && j < n)
            ++ j;
        v[vy[i].y].x = j;
    }
}
void lazy_update(int node, int l, int r, int p, int q, int sign)
{
    if (q < l || r < p || l > r)
        return;
    if (p <= l && q >= r)
    {
        arb[node] += sign;
        mval[node] += sign;
        return;
    }
    int lson = 2 * node, rson = 2 * node + 1, mid = (l + r) >> 1;

    lazy_update(lson, l, mid, p, q, sign);
    lazy_update(rson, mid + 1, r, p, q, sign);

    mval[node] = arb[node] + min(mval[lson], mval[rson]);
}
void solve()
{
    int i, j, k;

    for (i = 1; i <= n; ++ i)
        lazy_update(1, 1, n, 1, v[i].y, 1);
    for (i = 1, j = 1, k = 1; k <= v[n].x + 1; ++ k)
    {
        for (; i <= n && v[i].x <= k; ++ i)
            if (v[i].y != n)
                lazy_update(1, 1, n, v[i].y + 1, n, 1);

        for (; j <= n && v[j].x < k; ++ j)
            if (1 != v[j].y)
                lazy_update(1, 1, n, 1, v[j].y - 1, -1);
        sol = max(sol, mval[1]);
    }
}
void write()
{
    freopen("cadrane.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}