Cod sursa(job #28794)

Utilizator damaDamaschin Mihai dama Data 8 martie 2007 11:58:47
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 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;
	char line [32];
	
	for(i = 1; i <= n; ++i)
	{
		j = 0;
		fgets(line, 32, stdin);
		for(j = 0; '0' <= line[j] && line[j] <= '9'; ++j)
		{
            d[i].x *= 10;
		    d[i].x += line[j] - '0';
		}
		for(++j; '0' <= line[j] && line[j] <= '9'; ++j)
		{
            d[i].y *= 10;
			d[i].y += line[j] - '0';
		}
	//	scanf("%d%d", &d[i].x, &d[i].y);
	}
	sort(d + 1, d + n + 1, cmp);
	
	for(i = 1; i <= m; ++i)
	{
		j = 0;
		fgets(line, 32, stdin);
		for(j = 0;  '0' <= line[j] && line[j] <= '9'; ++j)
		{
            o[i].x *= 10;
		    o[i].x += line[j] - '0';
		}
		for(++j; '0' <= line[j] && line[j] <= '9'; ++j)
		{
            o[i].y *= 10;
			o[i].y += line[j] - '0';
		}
	}
	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;
}