Cod sursa(job #2827747)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 6 ianuarie 2022 12:08:20
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define debug cout << i << " " << j << " " << k << '\n'

using namespace std;
const int NMAX = 16001, QMAX = 100001;
const int COORDMAX = NMAX + 2 * QMAX + 1;
const int BUFFMAX = (1 << 20);


struct point {
  int x, y;
};
struct line {
  int lo, hi, x;
  int cv;
};

char rBuf[BUFFMAX];
int rpos;


unordered_map<int, int> normValY, normValX;
vector<int> ordpt[COORDMAX + 1], ordql[COORDMAX + 1], ordqr[COORDMAX + 1];
int aib[COORDMAX + 1];
int cY[COORDMAX + 1], cX[COORDMAX + 1];
int ans[QMAX + 1];
int indpt[NMAX + 1], indql[QMAX + 1], indqr[QMAX + 1];
point pts[NMAX + 1];
line qLeft[QMAX + 1];
line qRight[QMAX + 1];
FILE *fin;


inline void initInParser();
inline char getChar();
inline int getInt();
inline void normaliseAll(int tot);
inline void updAIB(int pos, int val, int n);
inline int queryAIB(int pos);
inline int queryInt(int lo, int hi);


int main() {
  int n, nrq, i, ind;
  fin = fopen("zoo.in", "r");
  initInParser();
  n = getInt();
  ind = 1;
  for (i = 0; i < n; i++) {
    indpt[i] = i;
    pts[i].x = getInt(), pts[i].y = getInt();
    cY[ind] = pts[i].y, cX[ind] = pts[i].x;
    ind++;
  }
  indpt[i] = n;
  nrq = getInt();
  for (i = 0; i < nrq; i++) {
    point p1, p2;
    p1.x = getInt(), p1.y = getInt(), p2.x = getInt(), p2.y = getInt();
    indql[i] = indqr[i] = i;
    cY[ind] = p1.y, cX[ind] = p1.x;
    ind++;
    cY[ind] = p2.y, cX[ind] = p2.x;
    ind++;
    qLeft[i].x = p1.x, qLeft[i].lo = p1.y, qLeft[i].hi = p2.y;
    qRight[i].x = p2.x, qRight[i].lo = p1.y, qRight[i].hi = p2.y;
  }
  indql[i] = indqr[i] = nrq;
  fclose(fin);

  normaliseAll(ind);

  for (i = 0; i < n; i++)
    ordpt[normValX.find(pts[i].x) -> second].push_back(i);
  for (i = 0; i < nrq; i++) {
    ordql[normValX.find(qLeft[i].x) -> second].push_back(i);
    ordqr[normValX.find(qRight[i].x) -> second].push_back(i);
  }

  ind--;
  for (i = 1; i <= ind; i++) {
    int len, k, j;
    len = ordql[i].size();
    for (j = 0; j < len; j++) {
      k = ordql[i][j];
      ans[k] -= queryInt(normValY.find(qLeft[k].lo) -> second, normValY.find(qLeft[k].hi) -> second);
    }

    len = ordpt[i].size();
    for (j = 0; j < len; j++) {
      k = ordpt[i][j];
      updAIB(normValY.find(pts[k].y) -> second, 1, ind);
    }

    len = ordqr[i].size();
    for (j = 0; j < len; j++) {
        k = ordqr[i][j];
        ans[k] += queryInt(normValY.find(qRight[k].lo) -> second, normValY.find(qRight[k].hi) -> second);
    }
  }
  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 tot) {
  sort(cY + 1, cY + tot);
  sort(cX + 1, cX + tot);

  for (int i = 1; i < tot; i++) {
    normValY.insert(pair<int, int>(cY[i], i));
    normValX.insert(pair<int, int>(cX[i], i));
  }
}

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);
}