Cod sursa(job #2639943)

Utilizator lucametehauDart Monkey lucametehau Data 4 august 2020 15:52:15
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <random>
#include <chrono>

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, passed;

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 <= 1000001; ind += lsb(ind))
    aib[ind] += val;
}

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

void buildTest() {
  unsigned t = chrono :: system_clock :: now().time_since_epoch().count();
  mt19937 gen(t);
  uniform_int_distribution <int> N(1, 10), dist(0, 1000);
  n = N(gen), m = N(gen);
  w = dist(gen), h = dist(gen);
  for(int i = 1; i <= n; i++)
    v[i].x = dist(gen), v[i].y = dist(gen);
  for(int i = 1; i <= m; i++)
    a[i].x = dist(gen), a[i].y = dist(gen);
}

int brut() {
  int ans = 0;
  for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++) {
      if(v[j].x <= a[i].x && a[i].x <= v[j].x + w && v[j].y <= a[i].y && a[i].y <= v[j].y + h) {
        ans++;
        break;
      }
    }
  }
  return ans;
}

void solve() {
  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;
  for(int i = 1; i <= n; i++)
    v[i].x++, v[i].y++;
  for(int j = 1; j <= m; j++)
    a[j].x++, a[j].y++;
  sort(v + 1, v + n + 1);
  sort(a + 1, a + m + 1);
  int j = 1, ans = 0;
  while(!q.empty())
    q.pop();
  for(int i = 1; i <= 1000001; i++)
    aib[i] = 0;
  for(int i = 1; i <= m; i++) {
    while(j <= n && v[j].x + w < a[i].x)
      j++;
    while(j <= n && v[j].x <= a[i].x && a[i].x <= v[j].x + w)
      q.push(j), update(v[j].y, 1), j++;
    while(!q.empty() && v[q.front()].x + w < a[i].x)
      update(v[q.front()].y, -1), q.pop();
    ans += (query(a[i].y) > query(a[i].y - h));
  }
  /*int x = brut();
  if(ans == x)
    cout << "Accepted!", passed++;
  else
    cout << "Wrong Answer!";*/
  cout << ans << "\n";
}

void tester() {
  for(int t = 1; t <= 10; t++) {
    cout << "Running test #" << t << "....\n";
    buildTest();
    solve();
  }
  cout << "Passed " << passed << " / 10 test. Good job!\n";
}

int main() {
  // tester();
  solve();
  return 0;
}