Cod sursa(job #1831074)

Utilizator antanaAntonia Boca antana Data 17 decembrie 2016 14:04:49
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAXN 16001

using namespace std;

vector <int> aint[MAXN*4];
vector <int>::iterator it1, it2;

struct fluffy{
  int x, y;

  bool operator <(const fluffy &aux) const {
    return x < aux.x;
  }
}v[MAXN];

int n, m, x1, x2, y11, y2, l1, l2, ans;

void dfs(int node, int left, int right)
{
  if(left == right)
  {
    aint[node].push_back(v[left].y);
    return;
  }

  unsigned int i, m = (left+right)/2;

  dfs(node*2, left, m);
  dfs(node*2+1, m+1, right);

  for(i=0; i<aint[node*2].size() + aint[node*2+1].size(); ++i)
    aint[node].push_back(0);

  merge(aint[node*2].begin(), aint[node*2].end(), aint[node*2+1].begin(), aint[node*2+1].end(), aint[node].begin());
}

void query(int node, int left, int right)
{
  if(left >= l1 && right <= l2)
  {
    it1 = lower_bound(aint[node].begin(), aint[node].end(), y11);
    it2 = upper_bound(aint[node].begin(), aint[node].end(), y2);
    ans += it2-it1;
    return;
  }

  int m = (left+right)/2;

  if(l1 <= m) query(node*2, left, m);
  if(l2 > m) query(node*2+1, right, m);
}

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

    int i, start, pas;

    scanf("%d", &n);

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

    sort(v+1, v+n+1);

    dfs(1, 1, n);

    scanf("%d", &m);

    start = 1;
    while((start<<1) <= n) start<<=1;

    for(i=1; i<=m; ++i)
    {
      scanf("%d%d%d%d", &x1, &y11, &x2, &y2);

      l1 = 0;
      for(pas=start; pas>=1; pas>>=1)
        if(v[l1+pas].x < x1)
            l1+=pas;

      l1++;

      l2 = 0;

      for(pas=start; pas>=1; pas>>=1)
        if(v[l2+pas].x <= x2)
          l2+=pas;

      ans = 0;
      query(1, 1, n);

      printf("%d\n", ans);
    }

    return 0;
}