Cod sursa(job #25550)

Utilizator sims_glAlexandru Simion sims_gl Data 4 martie 2007 12:54:25
Problema Ograzi Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.3 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define nm 50010
#define mm 100010
#define pm 2097152

struct point
{
	int x, y;
};

int n, m, w, h, c[pm], sol;
point d[mm], a[nm];

int cmp(point a, point b)
{
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}

void add(int pos, int val)
{
	++pos;

    while(pos < pm)
    {
    	c[pos] += val;
        pos += pos ^ (pos - 1) & pos;
    }
}

int query(int pos)
{
	int rez = 0;

    ++pos;

    while(pos > 0)
    {
    	rez += c[pos];
        pos -= pos ^ (pos - 1) & pos;
    }

    return rez;
}

int main()
{
	int i, open = 1, close = 1;

	freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);

    scanf("%d%d%d%d", &n, &m, &w, &h);

    for (i = 1; i <= n; ++i)
    	scanf("%d%d", &d[i].x, &d[i].y);

    for (i = 1; i <= m; ++i)
    	scanf("%d%d", &a[i].x, &a[i].y);

    sort(d + 1, d + n + 1, cmp);
    sort(a + 1, a + m + 1, cmp);

    for (i = 1; i <= m; ++i)
    {
        while(open <= n && d[open].x <= a[i].x)
        	add(d[open++].y, 1);
        
        while(close <= n && d[close].x + w < a[i].x)
        	add(d[close++].y, -1);

        if (query(a[i].y) - query(a[i].y - h - 1))
        	++sol;
    }

    printf("%d\n", sol);

	return 0;
}