Cod sursa(job #3342162)

Utilizator Lex._.Lex Guiman Lex._. Data 23 februarie 2026 10:58:14
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
#define VMAX 1000000
using namespace std;

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

int aib[VMAX+2];
vector<int> y_dreptunghi[VMAX+1];
vector<int> y_oi[VMAX+1];

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

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

int main()
{
    int n, m, w, h;
    in >> n >> m >> w >> h;
    for(int i=1; i<=n; i++)
    {
        int x, y;
        in >> x >> y;
        y_dreptunghi[x+w-1].push_back(y+w-1);
    }
    for(int i=1;  i<=m; i++)
    {
        int x, y;
        in >> x >> y;
        y_oi[x].push_back(y);
    }
    int ans=0;
    for(int i=1; i<=VMAX; i++)
    {
        for(auto& oaie : y_oi[i])
            update(oaie+1, 1);
        if(i>=w)
        {
            for(auto& oaie : y_oi[i-w])
                update(oaie+1, -1);
        }
        for(auto& dreptunghi : y_dreptunghi[i])
        {
            if(dreptunghi-w>0)
                ans+=query(dreptunghi+1)-query(dreptunghi-w);
        }
    }
    out << ans;

    return 0;
}