Cod sursa(job #25475)

Utilizator MariusMarius Stroe Marius Data 4 martie 2007 12:42:05
Problema Ograzi Scor 30
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.98 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const char iname[] = "ograzi.in";
const char oname[] = "ograzi.out";

#define MAX_N	  100007
#define MAX_T	  4194304
#define MAX_COORD 2000000

struct entry {
	int x, y;
	int sgn;
} ;

entry V[MAX_N], P[MAX_N];  int N, M, W, H, num;


void read_in(void) 
{
	freopen(iname, "r", stdin);
	int i;
	int x, y;
	scanf("%d %d", & N, & M);
	scanf("%d %d", & W, & H);
	for (i = 0; i < N; ++ i) {	/* zone */
		scanf("%d %d", & x, & y);
		/* latura din stanga */
		V[num].x = x, V[num].y = y, V[num].sgn = -1;
		num ++;
		/* latura din dreapta */
		V[num].x = x + W, V[num].y = y, V[num].sgn = +1;
		num ++;
	}
	for (i = 0; i < M; ++ i)
		scanf("%d %d", & P[i].x, & P[i].y), P[i].sgn = 0;
}

int mycmp(entry z, entry w) {
	if (z.x != w.x)
		return z.x < w.x;
	return z.sgn < w.sgn;
}

#define mid    (hi + lo) / 2
#define left   (n << 1)
#define right ((n << 1) + 1)

int A[MAX_T];

void update(int n, int lo, int hi, int a, int b, int cnt) 
{
	if ((a <= lo) && (hi <= b)) {
		A[n] += cnt;
		return ;
	}
	if (a <= mid)
		update(left, lo, mid, a, b, cnt);
	if (b > mid)
		update(right, mid + 1, hi, a, b, cnt);
}

int query(int n, int lo, int hi, int index)
{
	if (A[n] > 0)  
		return 1;
	if (hi == lo)
		return 0;
	if (index <= mid)
		return query(left, lo, mid, index);
	return query(right, mid + 1, hi, index);
}

int main(void)
{
	read_in();
	sort(V, V + num, mycmp);
	sort(P, P + M, mycmp);

	int cnt = 0;
	int i = 0;
	int j = 0;
	while (P[j].x < V[0].x) 
		j ++;
	for (; i < num && j < M; ) {
		int x = V[i].x;

		for (; i < num && V[i].x == x && V[i].sgn == -1; i ++)
			update(1, 0, MAX_COORD, V[i].y, V[i].y + H, +1);

		for (; j < M && P[j].x <= x; j ++) 
			if (query(1, 0, MAX_COORD, P[j].y) > 0)
				cnt ++;

		for (; i < num && V[i].x == x; i ++)
			update(1, 0, MAX_COORD, V[i].y, V[i].y + H, -1);
	}
	freopen(oname, "w", stdout);
	printf("%d\n", cnt);
	return 0;
}