Cod sursa(job #25670)

Utilizator victorsbVictor Rusu victorsb Data 4 martie 2007 14:08:07
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

#define Nmax 50005
#define Mmax 100005
#define x first
#define tip second.first
#define y second.second
#define mp make_pair

const int Ymax = 1000005;
int n, m, w, h, ct, vl, sol;
pair<int, pair<int, int> > ev[2 * Nmax + Mmax];
int aib[Ymax];
char s[32];

void citire()
{
    int i, a, b, ind, l;
    
    scanf("%d %d %d %d\n", &n, &m, &w, &h);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d\n", &a, &b);
        ev[++ct] = mp(a, mp(1, b));
        ev[++ct] = mp(a + w, mp(3, b));
    }
    
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d\n", &a, &b);
        ev[++ct] = mp(a, mp(2, b));
    }
}

void update(int pos)
{
    while (pos < Ymax)
    {
        aib[pos] += vl;
        pos += (pos ^ (pos - 1)) & pos;
    }
}

int query(int pos)
{
    int ret = 0;
    
    while (pos > 0)
    {
        ret += aib[pos];
        pos -= (pos ^ (pos - 1)) & pos;
    }
    
    return ret;
}

void solve()
{
    int i;
    
    sort(ev + 1, ev + ct + 1);
    
    for (i = 1; i <= ct; ++i)
    {
        if (ev[i].tip == 1)
        {
            vl = 1;
            update(ev[i].y);
            vl = -1;
            update(ev[i].y + h + 1);
        }
        else if (ev[i].tip == 3)
        {
            vl = -1;
            update(ev[i].y);
            vl = 1;
            update(ev[i].y + h + 1);
        }
        else if (ev[i].tip == 2)
        {
            if (query(ev[i].y) > 0)
                ++sol;
        }
    }
    printf("%d\n", sol);
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    citire();
    solve();
    return 0;
}