Cod sursa(job #2825412)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 4 ianuarie 2022 17:59:05
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.74 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define debug cout << pts[i].x << " " <<  qLeft[j].up.x << " " <<  qRight[k].up.x << '\n' << " ->  " << i << " " << j << " " << k << '\n'
#define debugInf cout << i << " " << j << " " << k << '\n' << '\n'

using namespace std;
const int NMAX = 16000, QMAX = 100000, INF = 1e9;
const int COORDMAX = NMAX + QMAX;

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

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];

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


int main() {
  int n, nrq, i, j, k, ind;
  query q;
  FILE *fin = fopen("zoo.in", "r");
  fscanf(fin, "%d", &n);
  ind = 1;
  for (i = 0; i < n; i++) {
    fscanf(fin, "%d%d", &pts[i].x, &pts[i].y);
    cX[ind] = pts[i].x, cY[ind] = pts[i].y;
    ind++;
  }
  fscanf(fin, "%d", &nrq);
  for (i = 0; i < nrq; i++) {
    fscanf(fin, "%d%d%d%d", &q.down.x, &q.down.y, &q.up.x, &q.up.y);
    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;
  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, n + nrq);
      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;
}
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);
  }
}

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

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

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

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

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

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