Cod sursa(job #1831524)

Utilizator antanaAntonia Boca antana Data 18 decembrie 2016 11:35:57
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAXN 16001

using namespace std;

vector <int> aint[MAXN*4];

struct fluffy{
  int x, y;

  bool operator <(const fluffy &aux) const {
    if(x == aux.x)
        return y < aux.y;
    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)
{
    int a, b;

    if(v[left].x >= l1 && v[right].x <= l2)
    {
        a = lower_bound(aint[node].begin(), aint[node].end(), y11) - aint[node].begin();
        b = upper_bound(aint[node].begin(), aint[node].end(), y2) - aint[node].begin();
        ans += b-a;
        return;
    }

    int m = (left+right)/2;

    if(left == right) return;
    if(l1 <= v[m].x) query(node*2, left, m);
    if(l2 >= v[m+1].x) query(node*2+1, m+1, right);
}

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

    int i;

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

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

      ans = 0;
      l1 = x1;
      l2 = x2;
      query(1, 1, n);

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

    return 0;
}