Cod sursa(job #3133715)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 26 mai 2023 17:25:16
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
#define L 16005
#define lsb(x) ((x ^ (x - 1)) & x)
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");

int n, m;
pair <int, int> a[L];
vector <int> t[L];
int X[L];

void add(int ind, int val){
  for (int i = ind; i <= n; i += lsb(i))
    t[i].push_back(val);
}

int sum(int p, int st, int dr){
  int ret = 0;
  for (int i = p; i; i -= lsb(i))
    ret += (upper_bound(t[i].begin(), t[i].end(), dr) - lower_bound(t[i].begin(), t[i].end(), st));
  return ret;
}

int query(int le, int ri, int st, int dr){
  return sum(ri, st, dr) - sum(le - 1, st, dr);
}

int main(){
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> a[i].first >> a[i].second;
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++)
    add(i, a[i].second);
  for (int i = 1; i <= n; i++)
    sort(t[i].begin(), t[i].end());
  for (int i = 1; i <= n; i++)
    X[i] = a[i].first;
  fin >> m;
  for (int i = 1; i <= m; i++){
    int x, y, xx, yy;
    fin >> x >> y >> xx >> yy;
    int x1 = lower_bound(X + 1, X + 1 + n, x) - X;
    int x2 = upper_bound(X + 1, X + 1 + n, xx) - X;
    fout << query(x1, x2 - 1, y, yy) << "\n";
  }
  return 0;
}