Cod sursa(job #1559853)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 31 decembrie 2015 17:40:06
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int Mx = 1 << 15;

struct point
{
    int x,y;
};

int n,m;
int sortx[Mx],tree[15][Mx],pos[15][Mx][2];
point ar[Mx];
int xx1,yy1,xx2,yy2;

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

    int mid = (l + r) / 2,i,j,k;

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

    for (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 A[],int val)
{
    int pos = 0;

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

    return pos;
}

int query(int lvl,int l,int r,int p1,int p2)
{
    int num = 0;

    if (xx1 <= l && r <= xx2)
    {
        if (p2 < l || p1 > r)
           return 0;

        if (p1 <= l && r <= p2)
           return (r - l + 1);

        if (p1 > 0 && tree[lvl][p1] == tree[1][yy1])
           p1--;

        num = p2 - p1;
    }
  else
    {
       int mid = (l + r) / 2;

       if (xx1 <= mid)
          num += query(lvl + 1,l,mid,pos[lvl][p1][0],pos[lvl][p2][0]);

       if (xx2 > mid)
          num += query(lvl + 1,mid + 1,r,pos[lvl][p1][1],pos[lvl][p2][1]);
    }

    return num;
}

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

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);

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

     build(1,1,n);

     scanf("%d\n",&m);

     /**for (int i = 1;i <= 6;i++)
     {
         for (int j = 1;j <= n;j++)
             printf("%d ",tree[i][j]);
         printf("\n");
     }*/

     while (m--)
     {
         scanf("%d %d %d %d",&xx1,&yy1,&xx2,&yy2);

         if (xx1 > sortx[n] || xx2 < sortx[1] || yy2 < tree[1][1] || yy1 > tree[1][n])
         {
             printf("0\n");
             continue;
         }

         xx1 = bs(sortx,xx1 - 1) + 1;
         xx2 = bs(sortx,xx2);
         yy1 = bs(tree[1],yy1 - 1) + 1;
         yy2 = bs(tree[1],yy2);

         printf("%d\n",query(1,1,n,yy1,yy2));
     }

   return 0;
}