Cod sursa(job #3342171)

Utilizator Lex._.Lex Guiman Lex._. Data 23 februarie 2026 11:25:51
Problema Ograzi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>
#define VMAX 1000001
#define NMAX 50000
#define MMAX 100000
#define x first
#define y second
using namespace std;

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

int aib[VMAX+1];
pair<int, int> dreptunghi[NMAX+1];
pair<int, int> oi[MMAX+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++)
    {
        in >> dreptunghi[i].x >> dreptunghi[i].y;
        dreptunghi[i].x+=w;
        dreptunghi[i].y+=h;
        dreptunghi[i].x++; dreptunghi[i].y++;
    }
    sort(dreptunghi+1, dreptunghi+n+1);
    for(int i=1; i<=m; i++)
    {
        in >> oi[i].x >> oi[i].y;
        oi[i].x++; oi[i].y++;
    }
    sort(oi+1, oi+m+1);
    int j=1, st=1, dr=1;
    int ans=0;
    for(int i=1; i<=VMAX; i++)
    {
        while(oi[dr].x==i && dr<=m)
        {
            update(oi[dr].y, 1);
            dr++;
        }
        if(i>w)
        {
            while(oi[st].x==i-w-1 && st<=dr)
            {
                update(oi[st].y, -1);
                st++;
            }
        }
        while(dreptunghi[j].x==i && j<=n)
        {
            ans+=query(dreptunghi[j].y);
            if(dreptunghi[j].y-h-1>0) ans-=query(dreptunghi[j].y-h-1);
            j++;
        }
    }
    out << ans;

    return 0;
}