Cod sursa(job #3342542)

Utilizator stefan_ciureaStefan Ciurea stefan_ciurea Data 24 februarie 2026 17:32:02
Problema Ograzi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second

using namespace std;

const int Valmax=1e6+5,Nmax=5e4+5,Mmax=1e5+5;

int aib[Valmax];
pii ograzi[Nmax],oi[Mmax];

int lsb(int x) {
    return x&(-x);
}
void update(int poz, int val) {
    for (int i=poz; i<Valmax; i+=lsb(i)) aib[i]+=val;
}
long long query(int poz) {
    long long s=0;
    for (int i=poz; i>0; i-=lsb(i)) s+=aib[i];
    return s;
}

int main()
{
    ifstream cin("ograzi.in");
    ofstream cout("ograzi.out");
    int n,m,h,w;
    cin>>n>>m>>w>>h;
    for (int i=1; i<=n; ++i) {
        cin>>ograzi[i].x>>ograzi[i].y;
        ograzi[i].x+=w+1;
        ograzi[i].y+=h+1;
    }
    sort(ograzi+1,ograzi+n+1);
    for (int i=1; i<=m; ++i) {
        cin>>oi[i].x>>oi[i].y;
        oi[i].x++;
        oi[i].y++;
    }
    sort(oi+1,oi+m+1);
    int j,st,dr,ans=0;
    j=st=dr=1;
    for (int i=1; i<Valmax; ++i) {
        while (oi[dr].x==i && dr<=m) update(oi[dr++].y,1);
        if (i>w) {
            while (oi[st].x==i-w-1 && st<=dr) update(oi[st++].y,-1);
        }
        while (ograzi[j].x==i && j<=n) {
            ans+=query(ograzi[j].y);
            if (ograzi[j].y>h+1) ans-=query(ograzi[j].y-h-1);
            j++;
        }
    }
    cout<<ans;
    cin.close();
    cout.close();
    return 0;
}