Cod sursa(job #1682211)

Utilizator stoianmihailStoian Mihail stoianmihail Data 10 aprilie 2016 00:45:05
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <stdio.h>
#include <vector>

using std::vector;

#define Nadejde 16000

struct pair {
  int x, y;

  pair() {

  }

  bool operator < (pair other) {
    return this -> y < other.y;
  }
};

int N, M;
pair sorted[Nadejde + 1];
vector <int> tree[4 * Nadejde + 1];

int count;
int x1, y1, x2, y2;

void sort(int begin, int end) {
  int b = begin, e = end;
  pair tmp, pivot = sorted[(b + e) >> 1];

  while (b <= e) {
    while (sorted[b] < pivot) {
      b++;
    }
    while (pivot < sorted[e]) {
      e--;
    }
    if (b <= e) {
      tmp = sorted[b];
      sorted[b++] = sorted[e];
      sorted[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

vector <int> join(vector <int> &left, vector <int> &right) {
  int i = 0, j = 0;
  vector <int> result;

  while ((i < left.size()) && (j < right.size())) {
    if (left[i] < right[j]) {
      result.push_back(left[i]);
      i++;
    } else {
      result.push_back(right[j]);
      j++;
    }
  }
  while (i < left.size()) {
    result.push_back(left[i]);
    i++;
  }
  while (j < right.size()) {
    result.push_back(right[j]);
    j++;
  }
  return result;
}

int search(vector <int> &val, int x) {
  int lo = -1, hi = val.size();

  while (hi - lo > 1) {
    int mid = (lo + hi) >> 1;
    if (val[mid] <= x) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return hi;
}

void build(int node, int left, int right) {
  if (left == right) {
    tree[node].push_back(sorted[left].x);
    return;
  }

  int mid = (left + right) >> 1;

  build(2 * node, left, mid);
  build(2 * node + 1, mid + 1, right);
  tree[node] = join(tree[2 * node], tree[2 * node + 1]);
}

void query(int node, int left, int right) {
  if ((y1 <= sorted[left].y) && (sorted[right].y <= y2)) {
    count += search(tree[node], x2) - search(tree[node], x1 - 1);
    return;
  }

  int mid = (left + right) >> 1;

  if (left == right) {
    return;
  }
  if (y1 <= sorted[mid].y) {
    query(2 * node, left, mid);
  }
  if (y2 >= sorted[mid + 1].y) {
    query(2 * node + 1, mid + 1, right);
  }
}

int main(void) {
  int i;
  FILE *f = fopen("zoo.in", "r");
  freopen("zoo.out", "w", stdout);

  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d %d", &sorted[i].x, &sorted[i].y);
  }

  sort(1, N);
  build(1, 1, N);

  fscanf(f, "%d", &M);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d %d %d", &x1, &y1, &x2, &y2);
    count = 0;
    query(1, 1, N);
    fprintf(stdout, "%d\n", count);
  }
  fclose(f);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}