(Andrew) Plundering Pirates - BIO 2025 Round 2

#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)x.size()
using namespace std;

const int MAXP = (1ll << 12) + 5;
int p, r;
int n, m;

int x[MAXP], y[MAXP];
int grid[MAXP][MAXP], sum[MAXP][MAXP];
map<int, int> cx, cy;
vector<int> xs, ys;

void compress() {
  for (int i = 1; i <= p; i++) {
    cin >> x[i] >> y[i];
    xs.push_back(x[i]);
    ys.push_back(y[i]);
  }
  sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
  sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
  int xptr = 1;
  for (ll i : xs) {
    cx[i] = xptr;
    ++xptr;
  }
  int yptr = 1;
  for (ll i : ys) {
    cy[i] = yptr;
    ++yptr;
  }
  n = yptr, m = xptr;
}

int calculate(int x2, int y2, int x1, int y1) {
  return sum[y2][x2] - sum[y2][x1 - 1] - sum[y1 - 1][x2] + sum[y1 - 1][x1 - 1];
}

int find_upper(int w, vector<int> &c) {
  int low = 0, high = sz(c), ans = sz(c);
  while (low <= high) {
    int mid = (low + high) / 2;
    if (c[mid] > w) {
      high = mid - 1, ans = mid;
    } else {
      low = mid + 1;
    }
  }
  --ans;
  return ans + 1;
}

int find_lower(int w, vector<int> &c) {
  int low = 0, high = sz(c), ans = sz(c);
  while (low <= high) {
    int mid = (low + high) / 2;
    if (c[mid] >= w) {
      high = mid - 1, ans = mid;
    } else {
      low = mid + 1;
    }
  }
  return ans + 1;
}

void solve() {
  cin >> p >> r;
  compress();
  for (int i = 1; i <= p; i++) {
    ++grid[cy[y[i]]][cx[x[i]]];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      sum[i][j] = sum[i][j - 1] + grid[i][j];
    }
  }
  for (int j = 1; j <= m; j++) {
    for (int i = 1; i <= n; i++) {
      sum[i][j] += sum[i - 1][j];
    }
  }
  for (int i = 1; i <= r; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (make_pair(x1, y1) > make_pair(x2, y2)) {
      swap(x1, x2);
      swap(y1, y2);
    }
    if (y1 <= y2) {
      // take upper_bound - 1 on x2, y2
      // take lower_bound on x1, y1
      int nx2 = find_upper(x2, xs);
      int ny2 = find_upper(y2, ys);
      int nx1 = find_lower(x1, xs);
      int ny1 = find_lower(y1, ys);
      cout << calculate(nx2, ny2, nx1, ny1) << '\n';
    } else {
      int nx2 = find_upper(x2, xs);
      int ny1 = find_upper(y1, ys);
      int nx1 = find_lower(x1, xs);
      int ny2 = find_lower(y2, ys);
      cout << calculate(nx2, ny1, nx1, ny2) << '\n';
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  solve();
  return 0;
}