Cod sursa(job #2108893)

Utilizator GoogalAbabei Daniel Googal Data 18 ianuarie 2018 21:59:59
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#pragma GCC diagnostic ignored "-fpermissive"
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 16000 + 10;

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

pair < int, int > v[1 + NMAX];
vector < int > aib[4*NMAX];
int n, m, x1, y1, x2, y2, st, dr;

void aibu(int nod, int st, int dr) {
  for(int i = st; i <= dr; i++)
    aib[nod].push_back(v[i].second);
  sort(aib[nod].begin(), aib[nod].end());

  if(st==dr)
    return;
  int fs = (nod << 1);
  int mid = (st + dr) / 2;
  aibu(fs, st, mid);
  aibu(fs + 1, mid + 1, dr);
}

int query(int nod, int st, int dr, int qst, int qdr) {
  int fs = (nod << 1);
  int mid = (st + dr) / 2;
  int ans = 0;

  if(st >= qst && dr <= qdr)
    return upper_bound(aib[nod].begin(),aib[nod].end(),y2) - lower_bound(aib[nod].begin(),aib[nod].end(),y1);

  if(mid >= qst)
    ans += query(fs, st, mid, qst, qdr);
  if(mid < qdr)
    ans += query(fs + 1, mid + 1, dr, qst, qdr);

  return ans;
}

int main() {
  in >> n;
  for(int i = 1; i <= n; i++)
    in >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    aibu(1, 1, n);

  in >> m;
  for(int i = 1; i <= m; i++) {
    in >> x1 >> y1 >> x2 >> y2;
    st = lower_bound(v + 1, v + n + 1, make_pair(x1, y1)) - v;
    dr = upper_bound(v + 1, v + n + 1, make_pair(x2, y2)) - v - 1;

    if(st > dr)
      out << "0\n";
    else
      out << query(1, 1, n, st, dr) << '\n';
  }

  in.close();
  out.close();
  return 0;
}