Cod sursa(job #1896481)

Utilizator TincaMateiTinca Matei TincaMatei Data 28 februarie 2017 18:35:35
Problema Zoo Scor 30
Compilator cpp Status done
Runda dopaj Marime 2.04 kb
#include <cstdio>
#include <algorithm>

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

struct Valuta {
  int tip, x, y1, y2;
  int *upd;
} v[MAX_N + 2*MAX_M];
int rez[MAX_M];

bool cmp(Valuta a, Valuta b) {
  return a.x < b.x || (a.x == b.x && a.tip < b.tip);
}

int aib[1+MAX_N+2*MAX_M];

inline int lastbit(int x) {
  return x & (-x);
}

inline void upd(int p, int x) {
  while(p <= MAX_E) {
    aib[p] += x;
    p += lastbit(p);
  }
}

inline int querySt(int p) {
  int rez = 0;
  while(p > 0) {
    rez += aib[p];
    p -= lastbit(p);
  }
  return rez;
}

int query(int a, int b) {
  return querySt(b) - querySt(a - 1);
}

bool cmp2(int *a, int *b) {
  return *a < *b;
}

int *p[MAX_N + 4 * MAX_M];

void normalize(int n) {
  int top = 0;
  for(int i = 0; i < n; ++i)
    if(v[i].tip == 0)
      p[top++] = &v[i].y1;
    else {
      p[top++] = &v[i].y1;
      p[top++] = &v[i].y2;
    }

  std::sort(p, p + top, cmp2);
  int last = *p[0];
  int j = 1;
  for(int i = 0; i < top; ++i) {
    if(*p[i] == last)
      *p[i] = j;
    else {
      last = *p[i];
      ++j;
      *p[i] = j;
    }
  }
}

int main() {
  int n, x, top = 0, m, x2, y2, y;
  FILE *fin = fopen("zoo.in", "r");
  FILE *fout = fopen("zoo.out", "w");
  fscanf(fin, "%d", &n);
  for(int i = 1; i <= n; ++i) {
    fscanf(fin, "%d%d", &x, &y);
    v[top].x = x;
    v[top].y1 = y;
    top++;
  }
  fscanf(fin, "%d", &m);
  for(int q = 0; q < m; ++q) {
    fscanf(fin, "%d%d%d%d", &x, &y, &x2, &y2);
    v[top].tip = 1;
    v[top].x = x - 1;
    v[top].y1 = y;
    v[top].y2 = y2;
    v[top].upd = &rez[q];
    top++;
    v[top].tip = 2;
    v[top].x = x2;
    v[top].y1 = y;
    v[top].y2 = y2;
    v[top].upd = &rez[q];
    top++;
  }
  fclose(fin);

  std::sort(v, v + top, cmp);
  normalize(top);
  for(int i = 0; i < top; ++i) {
    if(v[i].tip == 0)
      upd(v[i].y1, 1);
    else {
      int r = query(v[i].y1, v[i].y2);
      if(v[i].tip == 1)
        r = -r;
      *v[i].upd += r;
    }
  }

  for(int i = 0; i < m; ++i)
    fprintf(fout, "%d\n", rez[i]);

  fclose(fout);
  return 0;
}