Cod sursa(job #28763)

Utilizator damaDamaschin Mihai dama Data 8 martie 2007 11:27:01
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <algorithm>
#define nmax 1000001
#define omax 100002
#define dmax 50002

using namespace std;

struct point
{
	int x, y;
};

int n, m, w, h, aib[nmax], sol;
point o[omax], d[dmax];

bool cmp(point one, point two)
{
	return one.x < two.x || (one.x == two.x && one.y <= two.y);
}

void add(int val, int pos);
int query(int pos);

int main()
{
	freopen("ograzi.in","r",stdin);
	freopen("ograzi.out","w",stdout);
	
	scanf("%d%d%d%d", &n, &m, &w, &h);
	
	int i, j, first = 1, last = 0;
	
	for(i = 1; i <= n; ++i)
	{
		scanf("%d%d", &d[i].x, &d[i].y);
	}
	sort(d + 1, d + n + 1, cmp);
	
	for(i = 1; i <= m; ++i)
	{
		scanf("%d%d", &o[i].x, &o[i].y);
	}
	sort(o + 1, o + m + 1, cmp);

	for(i = 1; i <= m; ++i)
	{
		while(o[i].x >= d[last + 1].x && last < n)
		{
			++last;
			add(1, d[last].y);
		}
		while(o[i].x > d[first].x + w && first <= last)
		{
			add(-1, d[first].y);
			++first;
		}
		if(o[i].y - h - 1 < 0)
		    sol += query(o[i].y);
		else
			sol += query(o[i].y) - query(o[i].y - h - 1);
	}
	printf("%d", sol);


	return 0;
}

void add(int val, int pos)
{
	while(pos < nmax)
	{
		aib[pos] += val;
		pos += pos & (pos ^ (pos  - 1));
//		pos += ~(pos-1)&pos;
	}
}

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