Cod sursa(job #25699)

Utilizator victorsbVictor Rusu victorsb Data 4 martie 2007 14:13:11
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 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[64];

void citire()
{
    int i, a, b, ind, l;
    
    scanf("%d %d %d %d\n", &n, &m, &w, &h);
    for (i = 1; i <= n; ++i)
    {
        gets(s);
        ind = a = b = 0;
        l = strlen(s);
        while (s[ind] <= '9' && s[ind] >= '0')
        {
            a = a * 10 + s[ind] - '0';
            ++ind;
        }
        while (!(s[ind] <= '9' && s[ind] >= '0'))
            ++ind;
        while (ind < l && '0' <= s[ind] && s[ind] <= '9')
        {
            b = b * 10 + s[ind] - '0';
            ++ind;
        }
        
        ++a; ++b;
        
        ev[++ct] = mp(a, mp(1, b));
        ev[++ct] = mp(a + w, mp(3, b));
    }
    
    for (i = 1; i <= m; ++i)
    {
        gets(s);
        ind = a = b = 0;
        l = strlen(s);
        while (s[ind] <= '9' && s[ind] >= '0')
        {
            a = a * 10 + s[ind] - '0';
            ++ind;
        }
        while (!(s[ind] <= '9' && s[ind] >= '0'))
            ++ind;
        while (ind < l && '0' <= s[ind] && s[ind] <= '9')
        {
            b = b * 10 + s[ind] - '0';
            ++ind;
        }
        
        ++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;
}