Cod sursa(job #1682187)

Utilizator stoianmihailStoian Mihail stoianmihail Data 10 aprilie 2016 00:12:43
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.92 kb
#include <stdio.h>
#include <vector>

using std::vector;

#define MAX_SHL 16384
#define Nadejde 16000

struct pair {
  int x, y;

  pair() {

  }

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

  void write() {
    fprintf(stderr, "%d %d\n", this -> x, this -> y);
  }
};

int N, M;
pair sorted[Nadejde + 1];
vector <int> save[Nadejde + 1];
vector <int> tree[2 * MAX_SHL + 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);
  }
}

void normalize() {
  int i, j, ptr = 0;

  sort(1, N);
/*
  for (i = 1; i <= N; i++) {
    sorted[i].write();
  }
*/
  i = 1;
  while (i <= N) {
    ptr++;
    j = i;
    while ((j <= N) && (sorted[j].y == sorted[i].y)) {
      save[ptr].push_back(sorted[j].x);
      j++;
    }
    i = j;
  }
  N = ptr;
}

int cmpUp(int X, int Y) {
  return X < Y;
}

int cmpDown(int X, int Y) {
  return X <= Y;
}

int bSearch(int lo, int hi, int x, int cmp(int, int), int add) {
  while (hi - lo > 1) {
    int mid = (lo + hi) >> 1;
    if (cmp(sorted[mid].x, x)) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  return hi + add;
}
/*
void afis(vector<int>a) {
  for (int i=0;i<a.size();i++){
    fprintf(stderr, "%d,",a[i]);
  }
  fprintf(stderr, "\n");
}
*/
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++;
  }
  /*afis(left);
  afis(right);
  afis(result);
  */
  return result;
}

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

  //fprintf(stderr, "caut %d in ",x);
  //afis(val);

  while (hi - lo > 1) {
    int mid = (lo + hi) >> 1;
    if (val[mid] <= x) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  //fprintf(stderr, "isese %d\n", hi);
  return hi;
}

void build(int node, int left, int right) {
  if (left == right) {
    tree[node] = save[left];
    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 <= left) && (right <= y2)) {
    count += search(tree[node], x2) - search(tree[node], x1 - 1);
    return;
  }

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

  if (y1 <= mid) {
    query(2 * node, left, mid);
  }
  if (y2 > mid) {
    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);
  }

  normalize();
/*
  for (i = 1; i <= N; i++) {
    fprintf(stderr, "Linia %d: ", i);
    for (int j = 0; j < save[i].size(); j++) {
      fprintf(stderr, "%d, ", save[i][j]);
    }
    fprintf(stderr, "\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);
    //fprintf(stderr, "inte; %d %d %d %d\n",x1,y1,x2,y2);
    y1 = bSearch(0, N + 1, y1, cmpUp, 0);
    y2 = bSearch(0, N + 1, y2, cmpDown, -1);
    //fprintf(stderr, "dupa; %d %d %d %d\n",x1,y1,x2,y2);
    count = 0;
    if (y2) {
      query(1, 1, N);
    }
    fprintf(stdout, "%d\n", count);
  }
  fclose(f);
  fclose(stdout);

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