Cod sursa(job #1560009)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 1 ianuarie 2016 13:27:58
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int Ml = 15;
const int Mn = 1 << Ml;

struct point
{
    int x,y;
};

int n,m;
int sortx[Mn];
int tree[Ml][Mn],pos[Ml][Mn][2];
point p1,p2,ar[Mn];

bool comp(point a,point b)
{
    return a.x < b.x;
}

void build(int lvl,int l,int r)
{
    if (l == r)
    {
        tree[lvl][l] = ar[l].y;
        return;
    }

    int mid = (l + r) / 2;

    build(lvl + 1,l,mid);
    build(lvl + 1,mid + 1,r);

    for (int i = l,j = mid + 1,k = l;i <= mid || j <= r;k++)
        if (j > r || (i <= mid && tree[lvl + 1][i] < tree[lvl + 1][j]))
        {
            pos[lvl][k][0] = i;
            pos[lvl][k][1] = j - 1;
            tree[lvl][k] = tree[lvl + 1][i++];
        }
      else
        {
            pos[lvl][k][0] = i - 1;
            pos[lvl][k][1] = j;
            tree[lvl][k] = tree[lvl + 1][j++];
        }
}

int bs(int t[],int val)
{
    int idx = 0;

    for (int it = 1;it <= n;it *= 2)
        for (int i = it;i;i /= 2)
            if (idx + i <= n && t[idx + i] <= val)
               idx += i;

    return idx;
}

int query(int lvl,int l,int r,int st,int nd)
{
    int sol = 0;

    if (p1.x <= l && p2.x >= r)
    {
        if (nd < l || st > r)
           return 0;

        if (st <= l && nd >= r)
           return (r - l + 1);

        if (st > 0 && tree[lvl][st] == tree[1][p1.y])
           st--;

        sol = nd - st;
    }
  else
    {
        int mid = (l + r) / 2;

        if (p1.x <= mid)
           sol += query(lvl + 1,l,mid,pos[lvl][st][0],pos[lvl][nd][0]);

        if (p2.x > mid)
           sol += query(lvl + 1,mid + 1,r,pos[lvl][st][1],pos[lvl][nd][1]);
    }

    return sol;
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);

     scanf("%d",&n);

     for (int i = 1;i <= n;i++)
         scanf("%d %d",&ar[i].x,&ar[i].y);

     sort(ar + 1,ar + 1 + n,comp);
     build(1,1,n);

     for (int i = 1;i <= n;i++)
         sortx[i] = ar[i].x;

     scanf("%d",&m);

     while (m--)
     {
         scanf("%d %d %d %d",&p1.x,&p1.y,&p2.x,&p2.y);

         if (p1.x > sortx[n] || p2.x < sortx[1] || p1.y > tree[1][n] || p2.y < tree[1][1])
         {
             printf("0\n");
             return 0;
         }

         p1.x = bs(sortx,p1.x - 1) + 1;
         p2.x = bs(sortx,p2.x);
         p1.y = bs(tree[1],p1.y - 1) + 1;
         p2.y = bs(tree[1],p2.y);

         printf("%d\n",query(1,1,n,p1.y,p2.y));
     }
}