Cod sursa(job #25523)

Utilizator MariusMarius Stroe Marius Data 4 martie 2007 12:50:01
Problema Ograzi Scor 30
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.41 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
#define MAX_BUF   3600000

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

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

char buf[MAX_BUF];

void read_in(void) 
{
	freopen(iname, "r", stdin);
	int i;
	int x, y;
	scanf("%d %d\n", & N, & M);
	scanf("%d %d\n", & W, & H);
	
	int len = fread(buf, sizeof(char), MAX_BUF, stdin);
	char * p = buf;
	
	for (i = 0; i < N; ++ i) {	/* zone */
		while ((*p) < '0')  p ++;
		for (x = 0; (*p) >= '0'; p ++) 	x = x * 10 + (*p) - '0';
		while ((*p) < '0')  p ++;
		for (y = 0; (*p) >= '0'; p ++)	y = y * 10 + (*p) - '0';
		/* 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) {
		while ((*p) < '0')  p ++;
		for (x = 0; (*p) >= '0'; p ++) 	x = x * 10 + (*p) - '0';
		while ((*p) < '0')  p ++;
		for (y = 0; (*p) >= '0'; p ++)	y = y * 10 + (*p) - '0';
		P[i].x = x;
		P[i].y = y;
	}
}

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;
}