Cod sursa(job #2197694)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 22 aprilie 2018 18:17:56
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 16000;
const int MAX_M = 100000;

struct Point {
  int x, y;
  bool operator < (const Point& other) const {
    return this->y < other.y;
  }
}norm[MAX_N + 5];

struct PointIndex {
  int x, y, index;
}v[MAX_N + 5];

struct Query {
  int x, y, index, type;

  bool operator < (const Query& other) const {
    return this->y < other.y;
  }
}q[4 * MAX_N + 5];

int sol[MAX_M + 5];
int fndX[MAX_N + 5], fndY[MAX_N + 5];
int aib[MAX_N + 5];

bool cmp1(PointIndex a, PointIndex b) {
  return a.x < b.x;
}

bool cmp2(PointIndex a, PointIndex b) {
  return a.y < b.y;
}

void update(int poz, int n) {
  for (; poz <= n; poz += (poz & -poz))
    aib[poz]++;
}

int query(int poz) {
  int ans = 0;
  for (; poz; poz -= (poz & -poz))
    ans += aib[poz];
  return ans;
}

int bs(int st, int dr, int val, int v[]) {
  int last = 0;
  while (st <= dr) {
    int med = (st + dr) / 2;
    if (v[med] <= val) {
      last = med;
      st = med + 1;
    } else {
      dr = med - 1;
    }
  }
  return last;
}

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

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

  sort(v + 1, v + n + 1, cmp1);
  int k1 = 0;
  for (int i = 1; i <= n;) {
    k1++;
    int aux = v[i].x;
    fndX[k1] = aux;
    while (i <= n && v[i].x == aux) {
      norm[v[i].index].x = k1;
      i++;
    }
  }

  sort(v + 1, v + n + 1, cmp2);
  int k2 = 0;
  for (int i = 1; i <= n;) {
    k2++;
    int aux = v[i].y;
    fndY[k2] = aux;
    while (i <= n && v[i].y == aux) {
      norm[v[i].index].y = k2;
      i++;
    }
  }

  scanf("%d", &m);
  int k = 0;
  for (int i = 1; i <= m; ++i) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    int x, y;
    x1 = bs(1, k1, x1 - 1, fndX);
    y1 = bs(1, k2, y1 - 1, fndY);
    x2 = bs(1, k1, x2, fndX);
    y2 = bs(1, k2, y2, fndY);
    if (x2 != 0 && y2 != 0)
      q[++k] = {x2, y2, i, 1};
    if (x2 != 0 && y1 != 0)
      q[++k] = {x2, y1, i, -1};
    if (x1 != 0 && y2 != 0)
      q[++k] = {x1, y2, i, -1};
    if (x1 != 0 && y1 != 0)
      q[++k] = {x1, y1, i, 1};
  }

  return 0;
  sort(q + 1, q + k + 1);
  sort(norm + 1, norm + n + 1);

  int r = 1, t = 1;
  for (int i = 1; i <= k2 && r <= k; ++i) {
    while (t <= n && norm[t].y == i) {
      update(norm[t].x, k1);
      t++;
    }
    while (r <= k && q[r].y == i) {
      sol[q[r].index] += q[r].type * query(q[r].x);
      r++;
    }
  }

  for (int i = 1; i <= m; ++i)
    printf("%d\n", sol[i]);

  return 0;
}