Cod sursa(job #2639909)

Utilizator lucametehauDart Monkey lucametehau Data 4 august 2020 14:22:55
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

struct Point {
  int x, y;
  bool operator < (const Point &other) const {
    return (x < other.x || (x == other.x && y < other.y));
  }
};

int n, m, w, h;

Point v[50005], a[100005];
int aib[1000005];
queue <int> q;

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

void update(int ind, int val) {
  for(; ind <= (int)1e6; ind += lsb(ind))
    aib[ind] += val;
}

bool query(int ind) {
  int ans = 0;
  for(; ind; ind -= lsb(ind))
    ans += aib[ind];
  return (ans != 0);
}

int main() {
  cin >> n >> m >> w >> h;
  for(int i = 1; i <= n; i++)
    cin >> v[i].x >> v[i].y;
  for(int i = 1; i <= m; i++)
    cin >> a[i].x >> a[i].y;
  sort(a + 1, a + m + 1);
  sort(v + 1, v + n + 1);
  int j = 1, ans = 0;
  for(int i = 1; i <= m; i++) {
    while(v[j].x <= a[i].x && a[i].x <= v[j].x + w && j <= n)
      q.push(j), update(v[j].y, 1), update(v[j].y + h + 1, -1), j++;
    while(!q.empty() && v[q.front()].x + w < a[i].x)
      update(v[q.front()].y, -1), update(v[q.front()].y + h + 1, 1), q.pop();
    ans += query(a[i].y);
  }
  cout << ans;
  return 0;
}