Cod sursa(job #3225570)

Utilizator AswVwsACamburu Luca AswVwsA Data 17 aprilie 2024 23:30:48
Problema Ograzi Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <climits>
#define ll long long
using namespace std;

const int XMAX = 1e6;
const int MMAX = 1e5;

int aib[XMAX + 2];

void update(int poz, int val)
{
    for (; poz <= XMAX; poz += poz & -poz)
        aib[poz] += val;
}

void update(int l, int r, int val)
{
    update(l, val);
    update(r + 1, -val);
}

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

struct event
{
    int what;
    int l, r;
    int x;
};

bool operator <(event a, event b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.what < b.what;
}

event weee[2 * MMAX + 1];

signed main()
{
    ifstream cin("ograzi.in");
    ofstream cout("ograzi.out");
    int n, m, w, h, i;
    cin >> n >> m >> w >> h;
    int dim = 0;
    for (i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        y++;
        weee[++dim] = {1, y, y + w, x};
        weee[++dim] = {-1, y, y + w, x + h + 1};
    }
    for (i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        y++;
        weee[++dim] = {2, y, y, x};
    }
    sort(weee + 1, weee + 1 + dim);
    int ans = 0;
    for (i = 1; i <= dim; i++)
    {
        //cout << i << "\n";
        if (weee[i].what != 2)
        {
            update(weee[i].l, weee[i].r, weee[i].what);
        }
        else
            ans += query(weee[i].l);
    }
    cout << ans;
}