Cod sursa(job #2085649)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 10 decembrie 2017 15:24:56
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <algorithm>
#include <cstdio>

const int MAX_N = 16000;

struct Point {
  int x;
  int y;

  bool operator <(const Point &other) const {
    return this->x < other.x;
  }

  void scan() {
    scanf("%d%d", &x, &y);
  }
};

Point v[1 + MAX_N];
std::vector<int> aint[1 + 4 * MAX_N];
std::vector<int> X;

void buildAint(int node, int left, int right) {
  if (left == right) {
    aint[node].push_back(v[left].y);
    return;
  }
  int med = (left + right) >> 1;
  buildAint(2 * node, left, med);
  buildAint(2 * node + 1, med + 1, right);
  aint[node].resize(aint[2 * node].size() + aint[2*node + 1].size());
  std::merge(aint[2 * node].begin(), aint[2 * node].end(), aint[2 * node + 1].begin(), aint[2 * node + 1].end(), aint[node].begin());
}

int query(int node, int left, int right, int a, int b, int y1, int y2) {
  if (a <= left && right <= b) {
    return std::upper_bound(aint[node].begin(), aint[node].end(), y2) - std::lower_bound(aint[node].begin(), aint[node].end(), y1);
  }
  int med = (left + right) >> 1;
  int q1, q2;
  q1 = q2 = 0;
  if (a <= med) {
    q1 = query(2 * node, left, med, a, b, y1, y2);
  }
  if (b > med) {
    q2 = query(2 * node + 1, med + 1, right, a, b, y1, y2);
  }
  return q1 + q2;
}

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

  int N;
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    Point p;
    p.scan();
    v[i] = p;
  }
  std::sort(v + 1, v + N + 1);
  for (int i = 1; i <= N; i++) {
    X.push_back(v[i].x);
  }
  int M;
  scanf("%d", &M);
  buildAint(1, 1, N);
  for (int i = 1; i <= M; i++) {
    Point p1;
    Point p2;
    p1.scan();
    p2.scan();
    int a = std::lower_bound(X.begin(), X.end(), p1.x) - X.begin();
    int b = std::upper_bound(X.begin(), X.end(), p2.x) - X.begin() - 1;
    a++;
    b++;
    if (a <= N && b >= 1) {
      printf("%d\n", query(1, 1, N, a, b, p1.y, p2.y));
    } else {
      printf("0\n");
    }
  }
  return 0;
}