Cod sursa(job #6740)

Utilizator victorsbVictor Rusu victorsb Data 20 ianuarie 2007 20:14:50
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.38 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define Nmax 16384
#define x first
#define y second
#define pb push_back
#define sz(a) int((a).size())

using namespace std;

int n, m, i, j, a, b, vl, x1, y1, x2, y2, mem;
pair<int,int> punct[Nmax];
vector<int> l[Nmax*2];


void update(int nod, int st, int dr)
{
    if (a <= st && dr <= b)
    {
        l[nod].pb(vl);
    }
    else
    {
        int mij = (st + dr) >> 1;
        if (a <= mij)
            update(nod << 1, st, mij);
        if (mij < b)
            update((nod << 1) + 1, mij + 1, dr);
    }
}

void interclaseaza(int nod)
{
    int ind1 = 0, ind2 = 0, i;
    int nod1 = nod << 1, nod2 = (nod << 1) + 1;
    l[nod].resize(sz(l[nod1]) + sz(l[nod2]));
    for (i=1; i<=sz(l[nod1]) + sz(l[nod2]); ++i)
    {
        if (ind1 < sz(l[nod1]) && ind2 < sz(l[nod2]))
            if (l[nod1][ind1] < l[nod2][ind2])
            {
                l[nod][i-1] = (l[nod1][ind1]);
                ++ind1;
            }
            else
            {
                l[nod][i-1] = (l[nod2][ind2]);
                ++ind2;
            }
        else
            if (ind1 == sz(l[nod1]))
            {
                l[nod][i-1] = (l[nod2][ind2]);
                ++ind2;
            }
            else
            {
                l[nod][i-1] = (l[nod1][ind1]);
                ++ind1;
            }
    }
}

void ord(int nod, int st, int dr)
{
    if (st < dr)
    {
        int mij = (st + dr) >> 1;
        ord(nod << 1, st, mij);
        ord((nod << 1) + 1, mij + 1, dr);
        interclaseaza(nod);
    }
}

void solve()
{
    sort(punct+1, punct+n+1);
    for (i=1; i<=n; ++i)
    {
        a = b = i;
        vl = punct[i].y;
        update(1,1,n);
    }
    ord(1,1,n);
}

int cauta(int nod)
{
    //printf("nod %d\n", nod);
    int st,dr,mij,v1 = -1,v2 = -1;
    if (sz(l[nod]) == 0)
       return 0;
    
    st = 0;
    dr = sz(l[nod])-1;
    while (st <= dr)
    {
        mij = (st + dr) >> 1;
        if (y1 <= l[nod][mij])
        {
            v1 = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    //printf("v1 %d\n",v1);
    
    st = 0;
    dr = sz(l[nod])-1;
    while (st <= dr)
    {
        mij = (st + dr) >> 1;
        if (y2 >= l[nod][mij])
        {
            v2 = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    //printf("v2 %d\n", v2);
    if ((v1 != -1) && (v2 != -1))
        return v2 - v1 + 1;
    return 0;
    
}

int query(int nod, int st, int dr)
{
    if (a <= st && dr <= b)
    {
        return cauta(nod);
    }
    else
    {
        int mij = (st + dr) >> 1, ret = 0;
        if (a <= mij)
           ret += query(nod << 1, st, mij);
        if (mij < b)
           ret += query((nod << 1) + 1, mij + 1, dr);
        return ret;
    }
}

void solvequery()
{
    int st, dr, mij;
    scanf("%d\n", &m);
    /*
    for (i=1; i<=n; ++i)
        printf("%d ", punct[i].x);
    printf("\n");
    */
    for (i=1; i<=m; ++i)
    {
        scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
        a = b = 0;
        st = 1;
        dr = n;
        while (st <= dr)
        {
            mij = (st + dr) >> 1;
            if (punct[mij].x >= x1)
            {
                a = mij;
                dr = mij - 1;
            }
            else
                st = mij + 1;
        }
        //printf("a %d\n", a);
        st = 1;
        dr = n;
        while (st <= dr)
        {
            mij = (st + dr) >> 1;
            if (punct[mij].x <= x2)
            {
                b = mij;
                st = mij + 1;
            }
            else
                dr = mij - 1;
        }
        //printf("b %d\n", b);
        if (a == 0 || b == 0)
            printf("0\n");
        else
            printf("%d\n", query(1,1,n));
    }
    //printf("\n");
    //for (i=0; i<sz(l[1]); ++i)
    //    printf("%d ", l[1][i]);
}

void citire()
{
    scanf("%d\n", &n);
    for (i=1; i<=n; ++i)
        scanf("%d %d\n", &punct[i].x, &punct[i].y);
    solve();
    solvequery();
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    citire();
    /*
    for (i=0; i<Nmax * 2; ++i)
        mem += sz(l[i]);
    printf("memorie: %d\n", mem);*/
    return 0;
}