Cod sursa(job #3328167)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 6 decembrie 2025 16:45:48
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ograzi.in");
ofstream fout("ograzi.out");
const int MAXC = 1000000;
struct Operatie {
    int x, y1, y2;
    Operatie() {}
    Operatie(int _x, int _y1, int _y2): x(_x), y1(_y1), y2(_y2) {}
};
int n, m, w, h, i, j, rasp;
vector<Operatie> op;

int aib[MAXC + 2];
static inline void Update(int poz, int val) {
    poz++;
    while(poz <= MAXC) {
        aib[poz] += val;
        poz += (poz & -poz);
    }
}

static inline int Query(int poz) {
    int sum = 0;
    poz++;
    while(poz >= 1) {
        sum += aib[poz];
        poz -= (poz & -poz);
    }
    return sum;
}

static inline bool Cmp(Operatie a, Operatie b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y2 > b.y2;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m >> w >> h;
    for(i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;
        op.push_back(Operatie(x, y - 1, -1));
        op.push_back(Operatie(x, y + h,  1));

        op.push_back(Operatie(x + w, y - 1, -1));
        op.push_back(Operatie(x + w, y + h,  1));
    }
    for(i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        op.push_back(Operatie(x, y, -2));
    }

    sort(op.begin(), op.end(), Cmp);

    for(Operatie cur : op) {
        //cout << cur.x << " " << cur.y1 << " " << cur.y2 << "\n";
        if(cur.y2 == -2) rasp += Query(cur.y1) - Query(cur.y1 - 1);
        else Update(cur.y1, cur.y2);
    }
    fout << rasp;

    return 0;
}