Cod sursa(job #1517411)

Utilizator hrazvanHarsan Razvan hrazvan Data 4 noiembrie 2015 11:11:21
Problema Zoo Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 4.21 kb
#include <stdio.h>
#define MAXN 16000
#define MAXM 100000
#define CD 2000000000
#define MOD 666013
#define BUFF (1 << 20)
FILE *in;
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];
char ssin[BUFF];
int pin = BUFF;

inline char cif(char ch){
  if(ch >= '0' && ch <= '9')
    return 1;
  return 0;
}

inline char getcharr(){
  if(pin == BUFF){
    fread(ssin, 1, BUFF, in);
    pin = 0;
  }
  pin++;
  return ssin[pin - 1];
}

inline long long getnumm(){
  char ch = getcharr();
  long long rez = 0;
  int m;
  while(!cif(ch) && ch != '-')
    ch = getcharr();
  if(ch == '-'){
    m = -1;
    ch = getcharr();
  }
  else
    m = 1;
  while(cif(ch)){
    rez *= 10;
    rez += ch - '0';
    ch = getcharr();
  }
  return rez * m;
}

inline char cmp(int point, unsigned int py, int pt){
  unsigned int cy;
  int 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];
  unsigned int 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(unsigned 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(unsigned int y){
  unsigned 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(){
  in = fopen("zoo.in", "r");
  int n, m, i, a, b, c, d;
  n = (int)getnumm();
  for(i = 1; i <= n; i++){
    a = (int)getnumm();  b = (int)getnumm();
    xnorm[i] = a + CD + 1;
    xp[i] = a + CD + 1;
    yp[i] = b + CD + 1;
    point[i] = i;
    tip[i] = -2;
  }
  m = (int)getnumm();
  int dr = 1;
  for(i = 1; i <= m; i++){
    a = (int)getnumm();  b = (int)getnumm();
    c = (int)getnumm();  d = (int)getnumm();
    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;
}