Cod sursa(job #25478)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 4 martie 2007 12:42:37
Problema Ograzi Scor 30
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 3.21 kb
# include <stdio.h>

# define  _fin  "ograzi.in"
# define  _fout "ograzi.out"

# define  maxn  50002
# define  maxm  100002
# define  maxc  1000002
# define  logc  20

# define  isize 30


int n, m, w, h, sol;
int d[maxm][2], p[maxm][2];
int t[maxc*logc/isize + 1000];		// maxc * logc

char buf[20];


void readf()
{
	//freopen(_fin, "r", stdin);
	FILE *fin = fopen(_fin, "r");
	int i, j;
	
# define isalpha(x) ((x)>=0x30 && (x)<=0x39)
	for (fscanf(fin, "%d%d%d%d\n", &n, &m, &w, &h), i=1; i<=n; i++)
	{
		fgets(buf, 20, fin);
		for (j=0; buf[j] != ' '; j++) d[i][0] = d[i][0] * 10 + buf[j] - 0x30;
		while ( buf[j]==' ' ) ++j;
		for (; isalpha(buf[j]); j++) d[i][1] = d[i][1] * 10 + buf[j] - 0x30;
	}
//		 scanf("%d%d", &d[i][0], &d[i][1]);
	for (i=1; i<=m; i++)
	{
		fgets(buf, 20, fin);
		for (j=0; buf[j] != ' '; j++) p[i][0] = p[i][0] * 10 + buf[j] - 0x30;
		while ( buf[j]==' ' ) ++j;
		for (; isalpha(buf[j]); j++) p[i][1] = p[i][1] * 10 + buf[j] - 0x30;
	}
//		 scanf("%d%d", &p[i][0], &p[i][1]);
}

int qspoz(int st, int dr, int a[][2])
{
	int x = a[st][0], x2 = a[st][1];

	while ( st < dr )
	{
		while ( st<dr && a[dr][0]>=x ) dr--;
		a[st][0] = a[dr][0], a[st][1] = a[dr][1];
		while ( st<dr && a[st][0]<=x ) st++;
		a[dr][0] = a[st][0], a[dr][1] = a[st][1];
	}
	a[st][0] = x, a[st][1] = x2;
	return st;
}

void qs(int st, int dr, int a[][2])
{
	int m = qspoz(st, dr, a);
	if ( st<m ) qs(st, m-1, a);
	if ( m<dr ) qs(m+1, dr, a);
}

inline int l(int x) { return x<<1; }
inline int r(int x) { return (x<<1)|1; }

inline void mark(int x) { t[x/isize] |= (1<<(x%isize)); }
inline void unmark(int x)
{
	if ( t[x/isize] & ( 1 << (x%isize) ) )
		 t[x/isize] -=( 1 << (x%isize) );
}

inline int marked(int x) { return (t[x/isize]&(1<<(x%isize))) != 0; }

void _update(int n, int st, int dr, int a, int b, int v)
{
	if ( v==1 ) mark(n);
	else	  unmark(n);
//	t[n] += v;
	if ( st < dr )
	{
		int m = (st+dr)>>1;
		if ( a <= m ) _update( l(n), st, m, a, b, v);
		if ( m <  b ) _update( r(n), m+1, dr, a, b, v);
	}
}

// void update(int x, int v) { _update(1, 1, xmax, x, x, v); }

int _query(int n, int st, int dr, int a, int b)
{
	if ( a <= st && dr <= b ) return marked(n);
//	if ( a <= st && dr <= b ) return t[n];
	
	int m = (st+dr)>>1;
	return  ( a<=m ? _query(l(n), st, m, a, b) : 0 ) ||
			( m< b ? _query(r(n), m+1, dr, a, b) : 0 );
}

//int query(int a, int b) { return _query(1, 1, xmax, a, b); }
int trunc(int x) { return x>maxc?maxc:x; }

void solve()
{
	qs(1, n, d);
	qs(1, m, p);

	int del, ins, pct;
	del=ins=pct=1;

	while ( pct <= m )
	{
		// delete the points that must be deleted
		while ( d[del][0]+w < p[pct][0] && del < ins )	// do not delete uninserted
			_update(1, 1, maxc, d[del][1], trunc( d[del][1]+h ),-1), ++del;	// delete
		// insert rectangles that must be inserted
		while ( d[ins][0] <= p[pct][0] && ins <= n )
			_update(1, 1, maxc, d[ins][1], trunc( d[ins][1]+h ), 1), ++ins;	// insert
		
		// query one point
		sol += _query(1, 1, maxc, p[pct][1], p[pct][1]);

		++pct;
	}
}

void writef()
{
	freopen(_fout, "w", stdout);
	printf("%d\n", sol);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}