Cod sursa(job #1574)

Utilizator surcauvsurcau vasile surcauv Data 14 decembrie 2006 09:02:09
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.76 kb
# include <stdio.h>
# include <string.h>

# define  maxn  100002
# define  maxm  1300002

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


int dx[] = { -2,-1,-1,-1, 0, 0, 0, 0, 0, 1, 1, 1, 2 },
	dy[] = {  0, 1, 0,-1, 2, 1, 0,-1,-2, 1, 0,-1, 0 };


int sx[maxm][2], sy[maxm][2], n, m, t;
int d[maxn], st[maxn], sol;


int getcode(char c)
{
	switch(c)
	{
		case 'N' : return 0;
		case 'E' : return 1;
		case 'S' : return 2;
		case 'V' : return 3;
		
		default  : return -0xff;	// error, will not happen
	}
}
	
void readf()
{
	FILE *fin = fopen(_fin, "r");
	int i, x, y, j;
	char aux;
	
	for (fscanf(fin, "%d%d", &n, &m), i=1; i<=n; i++)
	{
		fscanf(fin, "%d %d\n", &x, &y);
		for (j=0; j<13; j++)
			if ( x+dx[j] && y+dy[j] )	// x and y are both different from 0
				sx[ ++t ][ 0 ] = x + dx[ j ],
				sx[  t  ][ 1 ] = y + dy[ j ];
	}
	
	for (i=1; i<=m; i++)
	{
		fscanf(fin, "%c %d\n", &aux, &x),
		d[i] = getcode(aux), st[i] = x;	// direction / steps
	}
	
	fclose(fin);
}

int qspoz(int st, int dr, int by, int v[maxn][2])
{
	int x1 = v[st][by], x2 = v[st][!by];
	
	while ( st < dr )
	{
		while ( st < dr && ( v[dr][by] > x1 || ( v[dr][by]==x1 && v[dr][!by]>=x2 ) ) ) dr--;
		v[st][0] = v[dr][0], v[st][1] = v[dr][1];
		while ( st < dr && ( v[st][by] < x1 || ( v[st][by]==x1 && v[st][!by]<=x2 ) ) ) st++;
		v[dr][0] = v[st][0], v[dr][1] = v[st][1];
	}
	
	v[st][by] = x1, v[st][!by] = x2;
	
	return st;
}

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

int  bsearchr(int st, int dr, int value, int by, int v[maxn][2])
{
	// rightmost value found
	int i, step;
	
	for (step=1; step<(dr-st); step<<=1);
	for (i=st; step; step>>=1)
		if ( i + step <= dr )
			if ( v[ i+step ][ by ] <= value )
				i += step;
				
	return v[i][by] == value ? i : -1;
}

int  bsearchl(int st, int dr, int value, int by, int v[maxn][2])
{
	// leftmost value found
	int i, step;
	
	for (step=1; step<(dr-st); step<<=1);
	for (i=dr; step; step>>=1)
		if ( i - step >= st )
			if ( v[ i-step ][ by ] >= value )
				i -= step;
				
	return v[i][by] == value ? i : -1;
}

int  bsearchr2(int st, int dr, int value, int by, int v[maxn][2])
{
	// rightmost value found
	int i, step;

	for (step=1; step<(dr-st); step<<=1);
	for (i=st; step; step>>=1)
		if ( i + step <= dr )
			if ( v[ i+step ][ by ] <= value )
				i += step;

	return i;
}

int  bsearchl2(int st, int dr, int value, int by, int v[maxn][2])
{
	// leftmost value found
	int i, step;
	
	for (step=1; step<(dr-st); step<<=1);
	for (i=dr; step; step>>=1)
		if ( i - step >= st )
			if ( v[ i-step ][ by ] >= value )
				i -= step;
				
	return i;
}


void presolve()
{
	memcpy(sy, sx, sizeof(sx));
	qs(1, t, 0, sx);
	qs(1, t, 1, sy);
}

inline int min(int a, int b) { return a<b?a:b; }
inline int max(int a, int b) { return a>b?a:b; }


void solve()
{
	int i, j, k, cnt;
	int cx, cy, nx, ny, l1, r1, l2, r2;
	
	for (cx=cy=0, i=1; i<=m; i++)
	{
		// from cx / cy, move
		if ( d[i] == 0 )
			nx=cx, ny=cy+st[i], ++cy;
		if ( d[i] == 1 )
			nx=cx+st[i], ny=cy, ++cx;
		if ( d[i] == 2 )
			nx=cx, ny=cy-st[i], --cy;
		if ( d[i] == 3 )
			nx=cx-st[i], ny=cy, --cx;
			
		if ( d[i] & 1 )		// E or V => move on X => same Y
		{
			if ( (l1 = bsearchl(1, t, cy, 1, sy)) != -1 )
			{
				cnt=0;
				// at least one trap on current y
				r1 = bsearchr(1, t, cy, 1, sy);	// will never be -1
				
				// can be in interval l1...r1
				l2 = bsearchl2(l1, r1, min(cx, nx), 0, sy);

				if ( l2 != -1 && min(cx, nx) <= sy[l2][0] )
				for (cnt=0, j=l2; j<=r1 && sy[j][0]<=max(cx, nx); )
				{
					++cnt;
					k=j;
					while ( sy[j][0] == sy[k][0] && j <= r1 && sy[j][0] <= max(cx, nx) )
						j++;
				}
//					for (++cnt, k=j; sy[j][0] == sy[k][0] && j<=t && sy[j][0]<=max(cx, nx); ++j);
					
				sol += cnt;
			}
		}
		else				// N or S => move on Y => same X
			if ( (l1 = bsearchl(1, t, cx, 0, sx)) != -1 )
			{
				cnt=0;
				// at least one trap on current x
				r1 = bsearchr(1, t, cx, 0, sx);
				
				// can be in l1...r1
				l2 = bsearchl2(l1, r1, min(cy, ny), 1, sx);
				
				if ( l2 != -1 && min(cy, ny) <= sx[l2][1] )
				for (cnt=0, j=l2; j<=r1 && sx[j][1]<=max(cy, ny); )
				{
					++cnt;
					k=j;
					while ( sx[j][1] == sx[k][1] && j <= r1 && sx[j][1]<=max(cy, ny) )
						j++;
				}
//					for (++cnt, k=j; sx[j][1] == sx[k][1] && j<=t && sx[j][1]<=max(cy, ny); j++);
					
				sol += cnt;
			}
			
		cx = nx, cy = ny;
	}
}

void writef()
{
	FILE *fout = fopen(_fout, "w");
	fprintf(fout, "%d\n", sol), fclose(fout);
}

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