Cod sursa(job #2825874)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 5 ianuarie 2022 10:35:27
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 16e3 + 5;

struct p {
  int x, y;
  bool operator<(const p& P) const {
    return x < P.x;
  }
};

int n;
p coord[N];
vector<int> aib[N];

int zeros(int x) {
  return x ^ (x & (x - 1));
}

void update(int poz, int val) {
  while (poz <= n) {
    aib[poz].push_back(val);
    poz += zeros(poz);
  }
}

int query(int poz, int y1, int y2) {
  int rez = 0;
  while (poz > 0) {
    int sus = upper_bound(aib[poz].begin(), aib[poz].end(), y2) - aib[poz].begin();
    int jos = lower_bound(aib[poz].begin(), aib[poz].end(), y1) - aib[poz].begin();
    rez += sus - jos;
    poz -= zeros(poz);
  }
  return rez;
}

int main() {
  ifstream cin("zoo.in");
  ofstream cout("zoo.out");
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> coord[i].x >> coord[i].y;
  //normalizez
  sort(coord + 1, coord + n + 1);
  //construiesc aib
  for (int i = 1; i <= n; ++i)
    update(i, coord[i].y);
  for (int i = 1; i <= n; ++i)
    sort(aib[i].begin(), aib[i].end());
  int q;
  cin >> q;
  while (q--) {
    p c1, c2;
    cin >> c1.x >> c1.y >> c2.x >> c2.y;
    int poz1 = lower_bound(coord + 1, coord + n + 1, c1) - coord;
    if (poz1 > 0) --poz1;
    int poz2 = upper_bound(coord + 1, coord + n + 1, c2) - coord;
    if (poz2 > 0) --poz2;
    cout << query(poz2, c1.y, c2.y) - query(poz1, c1.y, c2.y) << "\n";
  }
  cin.close();
  cout.close();
  return 0;
}