Cod sursa(job #931674)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 28 martie 2013 13:48:29
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
#define DIM 10000

using namespace std;

char buff[DIM];
int poz = 0;

void get(int &numar)
{
    numar = 0;
    bool semn = 0;
    while (buff[poz] < '0' || buff[poz] > '9')
    {
        if(buff[poz] == '-') semn = 1;
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }

    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }
    if(semn) numar = -numar;
}

struct Point
{
    int old, n, p;
};

Point Px[17000], Py[17000];
vector<int>Arb[400010];
int i, p, x, y, n, m, a, b, sol, Xmax;
int x1[100010], y1[100010], x2[100010], y2[100010];


bool cmp_p(Point a, Point b)
{
    return a.p < b.p;
}

bool cmp_x(Point a, Point b)
{
    return a.old < b.old;
}

bool cmp_y(Point a, Point b)
{
    return a.old < b.old;
}

bool Qcmp_x(Point a, int val)
{
    return a.old < val;
}

bool Qcmp_y(Point a, int val)
{
    return a.old < val;
}

void Normalizare()
{
    sort(Px+1, Px+n+1, cmp_x);
    Px[0].old = -int(2e9);
    for(i = 1; i <= n; i++)
        if(Px[i].old != Px[i-1].old) Px[i].n = Px[i-1].n + 2; else Px[i].n = Px[i-1].n;
    if(Px[n].old != int(2e9))
    {
        Px[n+1].old = int(2e9);
        Px[n+1].n = Px[n].n + 2;
    }

    sort(Py+1, Py+n+1, cmp_y);
    Py[0].old = -int(2e9);
    for(i = 1; i <= n; i++)
        if(Py[i].old != Py[i-1].old) Py[i].n = Py[i-1].n + 2; else Py[i].n = Py[i-1].n;
    if(Py[n].old != int(2e9))
    {
        Py[n+1].old = int(2e9);
        Py[n+1].n = Py[n].n + 2;
    }

    get(m);
    for(i = 1; i <= m; i++)
    {
        get(x);
        p = lower_bound(Px, Px+n+2, x, Qcmp_x) - Px;
        if(Px[p].old == x) x1[i] = Px[p].n; else x1[i] = Px[p].n - 1;

        get(x);
        p = lower_bound(Py, Py+n+2, x, Qcmp_y) - Py;
        if(Py[p].old == x) y1[i] = Py[p].n; else y1[i] = Py[p].n - 1;

        get(x);
        p = lower_bound(Px, Px+n+2, x, Qcmp_x) - Px;
        if(Px[p].old == x) x2[i] = Px[p].n; else x2[i] = Px[p].n - 1;

        get(x);
        p = lower_bound(Py, Py+n+2, x, Qcmp_y) - Py;
        if(Py[p].old == x) y2[i] = Py[p].n; else y2[i] = Py[p].n - 1;
    }
    Xmax = Px[n+1].n;
    sort(Px+1, Px+n+1, cmp_p);
    sort(Py+1, Py+n+1, cmp_p);
}

void Insert(int nod, int l, int r)
{
    if(l == r)
    {
        Arb[nod].push_back(y);
        return;
    }
    int m = (l+r)/2;
    if(x <= m) Insert(2*nod, l, m);
    if(x > m) Insert(2*nod+1, m+1, r);
}

void Merge(int nod, int l, int r)
{
    if(l == r)
    {
        sort(Arb[nod].begin(), Arb[nod].end());
        Arb[nod].push_back(int(2e9));
        return;
    }
    int m = (l+r)/2;
    Merge(2*nod, l, m);
    Merge(2*nod+1, m+1, r);
    Arb[nod].resize(Arb[2*nod].size() + Arb[2*nod+1].size());
    merge(Arb[2*nod].begin(), Arb[2*nod].end(), Arb[2*nod+1].begin(), Arb[2*nod+1].end(), Arb[nod].begin());
}

void Query(int nod, int l, int r)
{
    if(l >= x and r <= y)
    {
        int p1 = lower_bound(Arb[nod].begin(), Arb[nod].end(), a) - Arb[nod].begin();
        int p2 = upper_bound(Arb[nod].begin(), Arb[nod].end(), b) - Arb[nod].begin();
        sol += p2 - p1;
        return;
    }
    int m = (l+r)/2;
    if(x <= m) Query(2*nod, l, m);
    if(y > m) Query(2*nod+1, m+1, r);
}

int main()
{
    freopen("zoo.in", "r", stdin);
    ofstream fo("zoo.out");
    fread(buff, 1, DIM, stdin);
    get(n);
    for(i = 1; i <= n; i++)
    {
        get(Px[i].old);
        get(Py[i].old);
        Px[i].p = Py[i].p = i;
    }
    Normalizare();
    for(i = 1; i <= n; i++)
    {
        x = Px[i].n; y = Py[i].n;
        Insert(1, 1, Xmax);
    }
    Merge(1, 1, Xmax);
    for(i = 1; i <= m; i++)
    {
        x = x1[i]; y = x2[i];
        a = y1[i]; b = y2[i];
        sol = 0;
        Query(1, 1, Xmax);
        fo << sol << "\n";
    }
    return 0;
}