Cod sursa(job #676031)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 8 februarie 2012 16:51:25
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;

struct point {
  int x, y;
};

const int N = 17000, INF = 2000000005;

int n, rez, vx[N], corx[N];

point v[N];

vector <int> L[N], ai[4 * N];

void read() {
  assert(scanf("%d", &n));

  for (int i = 1; i <= n; ++i) {
    assert(scanf("%d%d", &v[i].x, &v[i].y));
    vx[++vx[0]] = v[i].x;
  }
}

int cautb1(int x, int v[N]) {
  int i = 0, pas = 1 << 14;

  for (i = 0; pas; pas >>= 1)
    if (i + pas <= v[0] && v[i + pas] < x)
      i += pas;

  return i + 1;
}

int cautb(int type, int x, int v[N]) {
  int i = 0, pas = 1 << 14;

  for (i = 0; pas; pas >>= 1)
    if (i + pas <= v[0] && v[i + pas] <= x)
      i += pas;

  if (type == 1) {
    if (v[i] == x)
      return i;

    return i + 1;
  }

  if (type == 2)
    return i;
}

void init() {
  vx[++vx[0]] = INF;
  vx[++vx[0]] = -INF;
  sort(vx + 1, vx + vx[0] + 1);

  for (int i = 1; i <= vx[0]; ++i)
    if (vx[i] == vx[i - 1])
      corx[i] = corx[i - 1];
    else
      corx[i] = corx[i - 1] + 1;

  for (int i = 1; i <= n; ++i)
    v[i].x = corx[cautb1(v[i].x, vx)];
}

void init_ai(int nod, int st, int dr) {
  if (st == dr) {
    for (int i = 0; i < (int)L[st].size(); ++i)
      ai[nod].push_back(L[st][i]);

    return;
  }

  int mid = (st + dr) / 2;

  init_ai(2 * nod, st, mid);
  init_ai(2 * nod + 1, mid + 1, dr);

  for (int i = 0, j = 0; i < (int)ai[2 * nod].size() || j < (int)ai[2 * nod + 1].size();)
    if (i >= (int)ai[2 * nod].size()) {
      ai[nod].push_back(ai[2 * nod + 1][j]);
      ++j;
    } else if (j >= (int)ai[2 * nod + 1].size()) {
      ai[nod].push_back(ai[2 * nod][i]);
      ++i;
    } else if (ai[2 * nod][i] < ai[2 * nod + 1][j]) {
      ai[nod].push_back(ai[2 * nod][i]);
      ++i;
    } else {
      ai[nod].push_back(ai[2 * nod + 1][j]);
      ++j;
    }
}

void make_ai() {
  for (int i = 1; i <= n; ++i)
    L[v[i].x].push_back(v[i].y);

  for (int i = 1; i <= corx[vx[0]]; ++i)
    sort(L[i].begin(), L[i].end());

  init_ai(1, 1, corx[vx[0]]);
}

// 1 - <=
// 2 - <
int cautbv(int type, int x, int nod) {
  int i = 0, pas = 1 << 16;

  for (i = -1; pas; pas >>= 1)
    if (i + pas < (int)ai[nod].size() && ((type == 1 && ai[nod][i + pas] <= x) || (type == 2 && ai[nod][i + pas] < x)))
      i += pas;

  return i;
}

int x1, y1, x2, y2;

void query(int nod, int st, int dr) {
  if (st > x2 || dr < x1)
    return;

  if (x1 <= st && dr <= x2) {
    rez += cautbv(1, y2, nod) - cautbv(2, y1, nod);

    return;
  }

  int mid = (st + dr) / 2;

  query(2 * nod, st, mid);
  query(2 * nod + 1, mid + 1, dr);
}

void solve() {
  int m;

  assert(scanf("%d", &m));

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

    rez = 0;
    x1 = corx[cautb(1, x1, vx)];
    x2 = corx[cautb(2, x2, vx)];

    if (x1 <= x2)
      query(1, 1, corx[vx[0]]);

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

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

  read();

  init();

  make_ai();

  solve();

  return 0;
}