Cod sursa(job #1517405)

Utilizator hrazvanHarsan Razvan hrazvan Data 4 noiembrie 2015 10:58:35
Problema Zoo Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <stdio.h>
#define MAXN 16000
#define MAXM 100000
#define CD 2000000000
#define MOD 666013
unsigned int xnorm[MAXN + 2 * MAXM];
unsigned int xp[MAXN + 1], yp[MAXN + 1], x1d[2 * MAXM + 1], x2d[2 * MAXM + 1], yd[2 * MAXM + 1], dt[2 * MAXM + 1];
int tip[MAXN + 2 * MAXM + 1], point[MAXN + 2 * MAXM + 1];
int rez[MAXM + 1];
int nr = 1;
int ult[MOD], hash[MAXN + 2 * MAXM + 1], next[MAXN + 2 * MAXM + 1];
int aib[MAXN + 2 * MAXM + 1];

inline char cmp(int point, int py, int pt){
  int cy, ct;
  if(point < 0){
    cy = yd[-point];
    ct = 1;
  }
  else{
    cy = yp[point];
    ct = -1;
  }
  if(cy > py)
    return 2;
  else  if(cy < py)
    return 0;
  else{
    if(ct < pt)
      return 0;
    else  if(ct > pt)
      return 2;
    else
      return 1;
  }
}

void qs(int st, int dr){
  int i = st, j = dr, mid = (st + dr) / 2, pt, aux;
  unsigned int py;
  if(point[mid] < 0){
    py = yd[-point[mid]];
    pt = 1;
  }
  else{
    py = yp[point[mid]];
    pt = -1;
  }
  while(i <= j){
    while(cmp(point[i], py, pt) == 0)
      i++;
    while(cmp(point[j], py, pt) == 2)
      j--;
    if(i <= j){
      aux = point[i];  point[i] = point[j];  point[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

void qs2(int st, int dr){
  int i = st, j = dr, piv = xnorm[(st + dr) / 2], aux;
  while(i <= j){
    while(xnorm[i] < piv)
      i++;
    while(xnorm[j] > piv)
      j--;
    if(i <= j){
      aux = xnorm[i];  xnorm[i] = xnorm[j];  xnorm[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs2(st, j);
  if(i < dr)
    qs2(i, dr);
}

inline void addhash(int y){
  int k = y % MOD, poz;
  poz = ult[k];
  while(poz != 0 && hash[poz] != y)
    poz = next[poz];
  if(poz == 0){
    hash[nr] = y;
    next[nr] = ult[k];
    ult[k] = nr;
    nr++;
  }
}

inline int care(int y){
  int k = y % MOD, poz;
  poz = ult[k];
  while(poz != 0 && hash[poz] != y)
    poz = next[poz];
  return poz;
}

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

int suma(int x){
  if(x == 0)
    return aib[0];
  return aib[x] + suma(x - ultb(x));
}

void addaib(int x){
  if(x <= nr){
    aib[x]++;
    addaib(x + ultb(x));
  }
}

inline void calc(int n, int m){
  int i;
  for(i = 1; i <= n + 2 * m; i++){
    if(point[i] < 0)
      rez[dt[-point[i]]] += tip[-point[i] + n] * (suma(care(x2d[-point[i]])) - suma(care(x1d[-point[i]])));
    else
      addaib(care(xp[point[i]]));
  }
}

int main(){
  FILE *in = fopen("zoo.in", "r");
  int n, m, i, a, b, c, d;
  fscanf(in, "%d", &n);
  for(i = 1; i <= n; i++){
    fscanf(in, "%d%d", &a, &b);
    xnorm[i] = a + CD + 1;
    xp[i] = a + CD + 1;
    yp[i] = b + CD + 1;
    point[i] = i;
    tip[i] = -2;
  }
  fscanf(in, "%d", &m);
  int dr = 1;
  for(i = 1; i <= m; i++){
    fscanf(in, "%d%d%d%d", &a, &b, &c, &d);
    xnorm[dr + n] = a + CD;
    x1d[dr] = a + CD;  x2d[dr] = c + CD + 1;
    yd[dr] = b + CD;
    dt[dr] = i;
    tip[dr + n] = -1;
    point[dr + n] = -dr;
    dr++;
    xnorm[dr + n] = c + CD + 1;
    x1d[dr] = a + CD;  x2d[dr] = c + CD + 1;
    yd[dr] = d + CD + 1;
    dt[dr] = i;
    tip[dr + n] = 1;
    point[dr + n] = -dr;
    dr++;
  }
  fclose(in);
  qs(1, n + 2 * m);
  qs2(1, n + 2 * m);
  for(i = 1; i <= n + 2 * m; i++)
    addhash(xnorm[i]);
  nr--;
  calc(n, m);
  FILE *out = fopen("zoo.out", "w");
  for(i = 1; i <= m; i++)
    fprintf(out, "%d\n", rez[i]);
  fclose(out);
  return 0;
}