Cod sursa(job #3193643)

Utilizator PowerPlantNICOLAS ANDREI MANASIA PowerPlant Data 15 ianuarie 2024 10:48:22
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <bits/stdc++.h>
#define lsb(x) ((x ^ (x - 1)) & x)

using namespace std;
ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");

int n, m, H, W;
int srt[300040];

struct puncte{
    int x, y;
};

puncte v[100010], p[50010];


int aib[200020];

void update_aib(int pos, int val){
    for(;pos <= n; pos += lsb(pos))
        aib[pos] += val;
    return ;
}

int query(int pos){
    int sum = 0;
    for(;pos > 0; pos -= lsb(pos))
        sum = sum + aib[pos];
    return sum;
}


bool cmp(puncte a, puncte b){
    return a.x < b.x;
}

int main()
{
    fin >> n >> m >> W >> H;
    int k = 0;
    for(int i = 1; i <= n; ++i){
        fin >> v[i].x >> v[i].y;
        srt[++k] = v[i].x;
        srt[++k] = v[i].y;
        }
    for(int i = 1; i <= m; ++i){
        fin >> p[i].x >> p[i].y;
        srt[++k] = p[i].x;
        srt[++k] = p[i].y;
        }
    sort(srt + 1, srt + k + 1);
    ///int L = unique(srt + 1, srt + k + 1) - srt - 1;
    for(int i = 1; i <= n; ++i)
    {
        v[i].x = lower_bound(srt + 1, srt + k + 1, v[i].x) - srt;
        v[i].y = lower_bound(srt + 1, srt + k + 1, v[i].y) - srt;
    }
    for(int i = 1; i <= m; ++i)
    {
        p[i].x = lower_bound(srt + 1, srt + k + 1, p[i].x) - srt;
        p[i].y = lower_bound(srt + 1, srt + k + 1, p[i].y) - srt;
    }


    sort(v + 1, v + n + 1, cmp);
    sort(p + 1, p + n + 1, cmp);

    int pos = 1, poz = 1, pos_ant = 1;
    int i = 1, ans = 0;
    while(pos <= n && poz <= m)
    {
        ///cout << query(100) << "\n";
        while(v[pos_ant].x + W < i && pos_ant <= n)
        {
            update_aib(v[pos_ant].y, -1);
            update_aib(v[pos_ant].y + H + 1, 1);
            ++pos_ant;
        }
        while(v[pos].x <= i && pos <= n)
        {
            update_aib(v[pos].y, 1);
            update_aib(v[pos].y + H + 1, -1);
            ++pos;
        }
        while(p[poz].x <= i && poz <= m)
        {
            ans = ans + query(p[poz].y);
            cout << query(p[poz].y) << "\n";
            ++poz;
        }
        ++i;
    }

    while(pos_ant <= n && poz <= m)
    {
        ///cout << query(100) << "\n";
        while(v[pos_ant].x + W < i && pos_ant <= n)
        {
            update_aib(v[pos_ant].y, -1);
            update_aib(v[pos_ant].y + H + 1, 1);
            ++pos_ant;
        }
        while(p[poz].x <= i && poz <= m)
        {
            ans = ans + query(p[poz].y);
            cout << query(p[poz].y) << "\n";
            ++poz;
        }
        ++i;
    }



    fout << ans;
    return 0;
}