Cod sursa(job #2225649)

Utilizator lucametehauDart Monkey lucametehau Data 27 iulie 2018 20:16:40
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("zoo.in");
ofstream cout ("zoo.out");

const int NMAX = 16e3;
const int MMAX = 1e5;

struct Point {
  int x, y;
  int ind;
  int tip;
};

int n, m, q;
int distx, disty;
int x1, y1, x2, y2;

Point v[1 + NMAX];
Point norm[1 + NMAX];
Point query[1 + 4 * MMAX];
int valx[1 + NMAX], valy[1 + NMAX];
int sol[1 + MMAX];
int aib[1 + NMAX];

bool comp1(Point a, Point b) {
  return a.x < b.x;
}

bool comp2(Point a, Point b) {
  return a.y < b.y;
}

int search(int v[], int n, int value) {
  int st = 1, dr = n, mid;
  while(st <= dr) {
    mid = (st + dr) / 2;
    if(v[mid] <= value)
      st = mid + 1;
    else
      dr = mid - 1;
  }
  return dr;
}

int lsb(int n) {
  return n & -n;
}

void Update(int poz) {
  for(; poz <= distx; poz += lsb(poz))
    aib[poz]++;
}

int Query(int poz) {
  int ans = 0;
  for(; poz; poz -= lsb(poz))
    ans += aib[poz];
  return ans;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> v[i].x >> v[i].y;
    v[i].ind = i;
  }
  sort(v + 1, v + n + 1, comp1);
  for(int i = 1; i <= n; i++) {
    distx++;
    int tmp = v[i].x;
    valx[distx] = tmp;
    while(i <= n && v[i].x == tmp) {
      norm[v[i].ind].x = distx;
      i++;
    }
    i--;
  }
  sort(v + 1, v + n + 1, comp2);
  for(int i = 1; i <= n; i++) {
    disty++;
    int tmp = v[i].y;
    valy[disty] = tmp;
    while(i <= n && v[i].y == tmp) {
      norm[v[i].ind].y = disty;
      i++;
    }
    i--;
  }
  cin >> m;
  for(int i = 1; i <= m; i++) {
    cin >> x1 >> y1 >> x2 >> y2;
    int val1, val2, val3, val4;
    val1 = search(valx, distx, x1 - 1);
    val2 = search(valy, disty, y1 - 1);
    val3 = search(valx, distx, x2);
    val4 = search(valy, disty, y2);
    if(val1 && val2)
      query[++q] = {val1, val2, i, 1};
    if(val1 && val4)
      query[++q] = {val1, val4, i, -1};
    if(val2 && val3)
      query[++q] = {val2, val3, i, -1};
    if(val3 && val4)
      query[++q] = {val3, val4, i, 1};
  }
  sort(query + 1, query + q + 1, comp2);
  sort(norm + 1, norm + n + 1, comp2);
  int j = 1, k = 1;
  for(int i = 1; i <= disty && j <= q; i++) {
    while(k <= n && norm[k].y == i) {
      Update(norm[k].x);
      k++;
    }
    while(j <= q && query[j].y == i) {
      sol[query[j].ind] += query[j].tip * Query(query[j].x);
      j++;
    }
  }
  for(int i = 1; i <= m; i++)
    cout << sol[i] << "\n";
  return 0;
}