Cod sursa(job #2827564)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 5 ianuarie 2022 21:39:07
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.01 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <unordered_map>
#define debug cout << i << " " << j << " " << k << '\n'

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


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

char rBuf[BUFFMAX];
int rpos;


unordered_map<int, int> normValY;
int aib[COORDMAX + 1];
int cY[COORDMAX + 1];
int ans[QMAX + 1];
int indpt[NMAX + 1], indql[QMAX + 1], indqr[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 tot);
inline void updAIB(int pos, int val, int n);
inline int queryAIB(int pos);
inline int queryInt(int lo, int hi);
inline bool cmpQueryLeft(int a, int b);
inline bool cmpQueryRight(int a, int b);
inline bool cmpPt(int a, int b);


int main() {
  int n, nrq, i, j, k, ind;
  query q;
  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;
    ind++;
  }
  indpt[i] = n;
  nrq = getInt();
  for (i = 0; i < nrq; i++) {
    indql[i] = indqr[i] = i;
    q.down.x = getInt(), q.down.y = getInt(), q.up.x = getInt(), q.up.y = getInt();
    cY[ind] = q.up.y;
    ind++;
    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;
  }
  indql[i] = indqr[i] = nrq;
  fclose(fin);

  sort(indpt, indpt + n, cmpPt);
  sort(indql, indql + nrq, cmpQueryLeft);
  sort(indqr, indqr + nrq, cmpQueryRight);
  normaliseAll(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[indql[j]].up.x <= pts[indpt[i]].x) {
      ans[indql[j]] -= queryInt(normValY.find(qLeft[indql[j]].down.y) -> second, normValY.find(qLeft[indql[j]].up.y) -> second);
      j++;
    }
    else if (pts[indpt[i]].x <= qRight[indqr[k]].up.x) {
      updAIB(normValY.find(pts[indpt[i]].y) -> second, 1, ind);
      i++;
    }
    else {
      ans[indqr[k]] += queryInt(normValY.find(qRight[indqr[k]].down.y) -> second, normValY.find(qRight[indqr[k]].up.y) -> second);
      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 tot) {
  sort(cY + 1, cY + tot);

  for (int i = 1; i < tot; i++)
    normValY.insert(pair<int, int>(cY[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);
}

inline bool cmpQueryLeft(int a, int b) {

  return qLeft[a].up.x < qLeft[b].up.x;
}
inline bool cmpQueryRight(int a, int b) {

  return qRight[a].up.x < qRight[b].up.x;
}

inline bool cmpPt(int a, int b) {
  return pts[a].x < pts[b].x;
}