Cod sursa(job #3187011)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 26 decembrie 2023 22:12:38
Problema Ograzi Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

const int V_MAX = 1000005;

struct BIT {
    int bit[4 * V_MAX + 5];

    static inline int lsb(int x) {
        return (x ^ (x - 1)) & x;
    }

    int query(int pos) {
        int ret = 0;
        for(; pos >= 1; pos -= lsb(pos)) {
            ret += bit[pos];
        }
        return ret;
    }

    void update(int pos, int val) {
        for(; pos <= V_MAX; pos += lsb(pos)) {
            bit[pos] += val;
        }
    }
};

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

int N, M, H, W;
Point P[V_MAX + 5];
vector <Point> E;
BIT T;

int main() {
#ifndef LOCAL
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> W >> H;
    for(int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        y++;
        E.push_back({x, y, 1});
        E.push_back({x + W + 1, y, -1});
    }
    for(int i = 1; i <= M; i++) {
        P[i].y++;
        cin >> P[i].x >> P[i].y;
    }

    sort(E.begin(), E.end());
    sort(P + 1, P + M + 1);

    int j = 0;
    int ans = 0;
    for(int i = 1; i <= M; i++) {
        while(j < (int)E.size() && E[j].x <= P[i].x) {
            T.update(E[j].y, E[j].t);
            j++;
        }
        ans += T.query(P[i].y) - T.query(P[i].y - H - 1);
    }

    cout << ans << "\n";
    return 0;
}