Cod sursa(job #2825579)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 4 ianuarie 2022 21:03:21
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.35 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;
const int NMAX = 16000, QMAX = 100000, INF = 1e9;
const int COORDMAX = NMAX + 2 * QMAX;
const int BUFFMAX = (1 << 14);


struct point {
  int x, y;
};
struct query {
  point up, down;
  int ind;
};

char rBuf[BUFFMAX];
int rpos;

int aib[COORDMAX + 1];
int cX[COORDMAX + 1], cY[COORDMAX + 1];
int ans[QMAX + 1];
point pts[NMAX + 1];
query qLeft[QMAX + 1];
query qRight[QMAX + 1];
FILE *fin;


inline void initInParser();
inline char getChar();
inline int getInt();
inline void normaliseAll(int n, int q, int tot);
inline void updAIB(int pos, int val, int n);
inline int queryAIB(int pos);
inline int queryInt(int lo, int hi);
inline int biSrch(int v[], int val, int n);
inline bool cmpQuery(query a, query b);
inline bool cmpPt(point a, point b);


int main() {
  int n, nrq, i, j, k, ind;
  query q;
  fin = fopen("zoo.in", "r");
  n = getInt();
  ind = 1;
  for (i = 0; i < n; i++) {
    pts[i].x = getInt(), pts[i].y = getInt();
    cX[ind] = pts[i].x, cY[ind] = pts[i].y;
    ind++;
  }
  nrq = getInt();
  for (i = 0; i < nrq; i++) {
    q.down.x = getInt(), q.down.y = getInt(), q.up.x = getInt(), q.up.y = getInt();
    cX[ind] = q.up.x, cY[ind] = q.up.y;
    ind++;
    cX[ind] = q.down.x, cY[ind] = q.down.y;
    ind++;
    qLeft[i].up.x = q.down.x, qLeft[i].up.y = q.up.y;
    qLeft[i].down.x = q.down.x, qLeft[i].down.y = q.down.y;
    qRight[i].up.x = q.up.x, qRight[i].up.y = q.up.y;
    qRight[i].down.x = q.up.x, qRight[i].down.y = q.down.y;
    qLeft[i].ind = qRight[i].ind = i;
  }
  fclose(fin);

  sort(pts, pts + n, cmpPt);
  sort(qLeft, qLeft + nrq, cmpQuery);
  sort(qRight, qRight + nrq, cmpQuery);
  normaliseAll(n, nrq, ind);

  pts[n].x = INF + 1;
  qLeft[nrq].up.x = INF + 2;
  qRight[nrq].up.x = INF;
  i = j = k = 0;
  ind--;
  while (i < n || j < nrq || k < nrq) {

    if (qLeft[j].up.x <= pts[i].x) {
      ans[qLeft[j].ind] -= queryInt(qLeft[j].down.y, qLeft[j].up.y);
      j++;
    }
    else if (pts[i].x <= qRight[k].up.x) {
      updAIB(pts[i].y, 1, ind);
      i++;
    }
    else {
      ans[qRight[k].ind] += queryInt(qRight[k].down.y, qRight[k].up.y);
      k++;
    }
  }

  FILE *fout = fopen("zoo.out", "w");
  for (i = 0; i < nrq; i++)
    fprintf(fout, "%d\n", ans[i]);
  fclose(fout);

  return 0;
}

inline void initInParser() {
    rpos = BUFFMAX;
}

inline char getChar() {
    if (rpos == BUFFMAX)
    {
        rpos = 0;
        fread(rBuf, sizeof(char), BUFFMAX, fin);
    }
    return rBuf[rpos++];
}
inline int getInt() {
    int res = 0;
    char ch;
    bool sign = 0;
    do
        ch = getChar();
    while (!isdigit(ch) && ch != '-');

    if (ch == '-') {
        sign = 1;
        ch = getChar();
    }
    do
       res = res * 10 + ch - '0';
    while (isdigit(ch = getChar()));
    if (sign)
        res = -res;
    return res;
}


inline void normaliseAll(int n, int q, int tot) {
  sort(cX + 1, cX + tot);
  sort(cY + 1, cY + tot);

  for (int i = 0; i < n; i++) {
    pts[i].x = biSrch(cX, pts[i].x, tot);
    pts[i].y = biSrch(cY, pts[i].y, tot);
  }

  for (int i = 0; i < q; i++) {
    qRight[i].up.x = biSrch(cX, qRight[i].up.x, tot);
    qRight[i].up.y = biSrch(cY, qRight[i].up.y, tot);
    qRight[i].down.x = biSrch(cX, qRight[i].down.x, tot);
    qRight[i].down.y = biSrch(cY, qRight[i].down.y, tot);

    qLeft[i].up.x = biSrch(cX, qLeft[i].up.x, tot);
    qLeft[i].up.y = biSrch(cY, qLeft[i].up.y, tot);
    qLeft[i].down.x = biSrch(cX, qLeft[i].down.x, tot);
    qLeft[i].down.y = biSrch(cY, qLeft[i].down.y, tot);
  }
}

inline void updAIB(int pos, int val, int n) {
  for (; pos <= n; pos += (pos & -pos))
    aib[pos] += val;
}

inline int queryAIB(int pos) {
  int s = 0;
  for (; pos > 0; pos -= (pos & -pos))
    s += aib[pos];
  return s;
}

inline int queryInt(int lo, int hi) {
  if (lo > hi)
    swap(lo, hi);
  return queryAIB(hi) - queryAIB(lo - 1);
}

inline int biSrch(int v[], int val, int n) {
  int step = (1 << 17), pos = 0;
  while (step)
  {
    if (pos + step < n && v[pos + step] < val)
      pos += step;
    step >>= 1;
  }
  return pos + 1;
}

inline bool cmpQuery(query a, query b) {
  return a.up.x < b.up.x;
}

inline bool cmpPt(point a, point b) {
  return a.x < b.x;
}