Cod sursa(job #25813)

Utilizator wefgefAndrei Grigorean wefgef Data 4 martie 2007 14:50:18
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define mp make_pair
#define x first
#define y second.first
#define z second.second
#define pb push_back
#define sz size()
#define lsb(a) (a & (a ^ (a-1)))
#define Rmax 1000005

int n, m, w, h;
vector< pair< int, pair<int, int> > > v;
int aib[Rmax];

void readdata()
{
	freopen("ograzi.in", "r", stdin);
	freopen("ograzi.out", "w", stdout);
	
	int i, a, b;
	char s[16], poz, lung;
	
	scanf("%d %d %d %d\n", &n, &m, &w, &h);
	for (i = 0; i < n; ++i)
	{
		fgets(s, 16, stdin);
		lung = strlen(s);
		a = b = 0;
		poz = 0;
		while (s[poz] != ' ')
			a = a*10 + s[poz++]- '0';
		++poz;
		while (poz < lung)
			b = b*10 + s[poz++]-'0';
		++a, ++b;
		
		v.pb( mp(a, mp(0, b)) );
		v.pb( mp(a+w, mp(2, b)) );
	}
	for (i = 0; i < m; ++i)
	{
		fgets(s, 16, stdin);		
		lung = strlen(s);
		a = b = 0;
		poz = 0;
		while (s[poz] != ' ')
			a = a*10 + s[poz++]- '0';
		++poz;
		while (poz < lung)
			b = b*10 + s[poz++]-'0';
		++a, ++b;
		
		v.pb( mp(a, mp(1, b)) );		
	}
}

void update(int k, int val)
{
	while (k < Rmax)
	{
		aib[k] += val;
		k += lsb(k);
	}
}

int query(int k)
{
	int sum = 0;
	while (k)
	{
		sum += aib[k];
		k -= lsb(k);
	}
	return sum > 0;	
}

void solve()
{
	int i, lim = v.sz, rez = 0;
	
	sort(v.begin(), v.end());
	
	for (i = 0; i < lim; ++i)
	{
		if (v[i].y == 0)
		{
			update(v[i].z, 1);
			update(v[i].z+h+1, -1);
		}		
		if (v[i].y == 2)
		{
			update(v[i].z, -1);
			update(v[i].z+h+1, 1);
		}
		if (v[i].y == 1)

			rez += query(v[i].z);
	}
	printf("%d\n", rez);
}

int main()
{
	readdata();
	solve();
	return 0;
}