Cod sursa(job #1551713)

Utilizator akaprosAna Kapros akapros Data 16 decembrie 2015 14:03:39
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.27 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 16002
#define maxM 100002
using namespace std;
int n, N, m, sum, arb[(maxN + maxM) * 8], sol[maxM], s[maxM];
int lx, ly;
struct point
{
    int x, y;
} v[maxN], cx[(maxN + maxM)], cy[(maxN + maxM)];
struct fst
{
    int x, y, t;
    bool z;
} w[maxM * 2];
struct corner
{
    point a, b;
    int p;
    bool z, t;
} q[maxM];
int cmp(const point a, const point b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
int Cmp(const fst a, const fst b)
{
    if (a.x == b.x)
        return a.z > b.z;
    return a.x < b.x;
}
void update(int node, int l, int r, int pos, int val)
{
    if (l == r)
    {
        arb[node] += val;
        return ;
    }
    int mid = (l + r) >> 1, lson = 2 * node, rson = lson + 1;
    if (pos <= mid)
        update(lson, l, mid, pos, val);
    else
        update(rson, mid + 1, r, pos, val);
    arb[node] = arb[lson] + arb[rson];
}
void query(int node, int l, int r, int x, int y)
{
    if (x > r || y < l || r < l)
        return ;

    if (x <= l && y >= r)
    {
        sum += arb[node];
        return ;
    }
    int mid = (l + r) >> 1, lson = 2 * node, rson = lson + 1;
    if (x <= mid)
        query(lson, l, mid, x, y);
    if (y > mid)
        query(rson, mid + 1, r, x, y);
    arb[node] = arb[lson] + arb[rson];
}
void read()
{
    int i;
    freopen("zoo.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &v[i].x, &v[i].y);
        cx[++ lx].x = v[i].x;
        cx[lx].y = i;

        cy[++ ly].x = v[i].y;
        cy[ly].y = i;
    }
    scanf("%d", &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d %d %d", &q[i].a.x, &q[i].a.y,&q[i].b.x, &q[i].b.y);
        q[i].p = i;
        cx[++ lx].x = q[i].a.x;
        cx[lx].y = i + n;

        cy[++ ly].x = q[i].a.y;
        cy[ly].y = i + n;

        cx[++ lx].x = q[i].b.x;
        cx[lx].y = i + n;

        cy[++ ly].x = q[i].b.y;
        cy[ly].y = i + n;
    }
}
void solve()
{
    int i, p, j;
    sort(cx + 1, cx + lx + 1, cmp);
    sort(cy + 1, cy + ly + 1, cmp);
    N = (n + m + 1) * 2;
    for (i = 1; i <= lx; ++ i)
    {
        p = i;
        do
        {
            if (cx[i].y <= n)
                v[cx[i].y].x = p;
            else
            {
                j = cx[i].y - n;
                if (!q[j].z)
                {
                    q[j].a.x = p;
                    q[j].z = 1;
                }
                else
                    q[j].b.x = p;

                w[j * 2 - 1].x = q[j].a.x;
                w[j * 2].x = q[j].b.x;
                w[j * 2 - 1].z = 1;
                w[j * 2 - 1].t = w[j * 2].t = j;
            }
           ++ i;
        }while (cx[i - 1].x == cx[i].x && i <= lx);
        -- i;
    }
    for (i = 1; i <= ly; ++ i)
    {
        p = i;
        do
        {
            if (cy[i].y <= n)
                v[cy[i].y].y = p;
            else
            {
                j = cy[i].y - n;
                if (!q[j].t)
                {
                    q[j].a.y = p;
                    q[j].t = 1;
                }
                else
                    q[j].b.y = p;
                w[j * 2 - 1].y = q[j].a.y;
                w[j * 2].y = q[j].b.y;
            }
            ++ i;
        }while (cy[i - 1].x == cy[i].x && i <= ly);
        -- i;
    }
    sort(v + 1, v + n + 1, cmp);
    sort(w + 1, w + 2 * m + 1, Cmp);
    p = 1; j = 1;
    while (v[p].x < w[1].x)
        ++ p;
    for (i = 1; i <= 2 * m; ++ i)
    {
        if (w[i].z)
        {
            sum = 0;
            query(1, 1, N, q[w[i].t].a.y, q[w[i].t].b.y);
            s[w[i].t] = sum;
        }
        while (v[p].x <= w[i].x && p <= n)
        {
            update(1, 1, N, v[p].y, 1);
            ++ p;
        }
        if (!w[i].z)
        {
            sum = 0;
            query(1, 1, N, q[w[i].t].a.y, q[w[i].t].b.y);
            sol[w[i].t] = sum - s[w[i].t];
        }
    }
}
void write()
{
    int i;
    freopen("zoo.out", "w", stdout);
    for (i = 1; i <= m; ++ i)
        printf("%d\n", sol[i]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}