Cod sursa(job #111097)

Utilizator mariusdrgdragus marius mariusdrg Data 28 noiembrie 2007 17:19:03
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define pb push_back
#define vi vector <int>


const int maxn = 16001;

vi vectx;
vi arb[maxn * 4 + 1000];
int mar;
int n;
int m;
int x[maxn],y[maxn];
int nod;
int i;
int j;
int sz[maxn * 4 + 1000];
int x1,x2,y1,y2;
int nr;

const int inf = 2000000010;


int bs1(int nod,int val)
{
        int n = sz[nod] - 1;
        if (n == -1) return 0;
        int p;
        int x = 0;
        for(p = 1;p <= n;p <<= 1);
        for(;p;p >>= 1)
                 if (x + p <= n)
                 {
                        if (arb[nod][x + p] <= val)
                        {
                                x += p;
                        }
                 }
        if (val < arb[nod][x]) return x - 1;
        return x;
}

int bs(int val)
{
        int n = mar;
        int p;
        int x = 0;
        for(p = 1;p <= n;p <<= 1);
        for(;p;p >>= 1)
                 if (x + p <= n)
                 {
                        if (vectx[x + p] <= val)
                        {
                                x += p;
                        }
                 }
        if (val < vectx[x]) return x - 1;
        return x;

}

int querry(int st,int dr,int nod)
{

        int mid = (st + dr) / 2;
        if (x1 <= st && x2 >= dr)
        {
                return bs1(nod,y2) - bs1(nod,y1 - 1);
        }
        if (mid >= x2)  return querry(st,mid,nod * 2);
        if (mid < x1) return querry(mid + 1,dr,nod * 2 + 1);
        return querry(st,mid,nod * 2) + querry(mid + 1,dr,nod * 2 + 1);
}

void update(int st,int dr,int nod)
{
        int mid = (st + dr) / 2;
        if (st == dr && x1 == st)
        {
                arb[nod].pb(y[i]);
                return ;
        }
        if (x1 <= mid) update(st,mid,nod * 2);
        if (x1 > mid) update(mid + 1,dr,nod * 2 + 1);
        arb[nod].pb(y[i]);

}

int main()
{
        freopen("zoo.in","r",stdin);
        freopen("zoo.out","w",stdout);
        scanf("%d",&n);
        vectx.pb(-inf - 1);
        vectx.pb(-inf);
        for(i = 1;i <= n; ++i)
        {
                scanf("%d %d",&x[i],&y[i]);
                vectx.pb(x[i]);
        }
        mar = vectx.size() - 1;
        vectx.pb(inf);
        sort(vectx.begin(),vectx.end());
        for(i = 1;i <= n; ++i)
        {
                x1 = bs(x[i]);
                update(1,n + 2,1);
        }
        for(i = 1;i <= 4 * n; ++i)
        {
                arb[i].pb(-inf);
                sort(arb[i].begin(),arb[i].end());
                sz[i] = arb[i].size();
        }
        
        scanf("%d",&m);
        for(i = 1;i <= m; ++i)
        {
                scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                int aux = x1;
                x1 = bs(x1);
                if (aux != vectx[x1])  ++x1;
                
                x2 = bs(x2);
                printf("%d\n",querry(1,n + 2,1));
        }



        return 0;
}