Cod sursa(job #1555654)

Utilizator borcanirobertBorcani Robert borcanirobert Data 23 decembrie 2015 12:45:03
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

ifstream fin("zc.in");
ofstream fout("zc.out");

const int MAX = 100005;
const int INF = 0x3f3f3f3f;
const int obsi[] = { -2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2 };
const int obsj[] = { 0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0 };
const int di[] = { -1, 0, 1, 0 };
const int dj[] = { 0, 1, 0, -1 };

vector<pair<int, int>> o1;
vector<pair<int, int>> o2;
char D;
int p;
int N, M;
int no;
int nro;

int BinarySearch1( vector<pair<int, int>> v, pair<int, int> val );
int BinarySearch2( vector<pair<int, int>> v, pair<int, int> val );

int main()
{
	int i, j;
	int x, y, p, p1, p2;
	
	fin >> N >> M;
	for ( i = 1; i <= N; i++ )
	{
		fin >> x >> y;
		
		for ( j = 0; j < 13; j++ )
		{
			o1.push_back( make_pair( (x + obsi[j]), (y + obsj[j]) ) );
		}
	}
//	o1.push_back( make_pair(INF, INF) );
	sort( o1.begin(), o1.end() );
	
	for ( const auto& n : o1 )
		if ( o1[no] != n )
		{
			o1[++no] = n;
			o2.push_back( make_pair( n.second, n.first ) );
		}
	//o2.push_back( make_pair(INF, INF) );
	
	sort( o2.begin(), o2.end() );
	
	x = y = 0;
	for ( i = 1; i <= M; i++ )
	{
		fin >> D >> p;
		
		if ( D == 'E' || D == 'V' )
		{			
			if ( D == 'E' )
			{
				nro += ( upper_bound( o2.begin(), o2.end(), make_pair(y, x + p) ) - lower_bound( o2.begin(), o2.end(), make_pair(y, x) ) );
				x += p;
			}
			else
			{
				nro += ( upper_bound( o2.begin(), o2.end(), make_pair(y, x) ) - lower_bound( o2.begin(), o2.end(), make_pair(y, x - p) ) );
				x -= p;
			}
		}
		else
		{
			if ( D == 'N' )
			{
				nro += ( upper_bound( o1.begin(), o1.end(), make_pair(x, y + p) ) - lower_bound( o1.begin(), o1.end(), make_pair(x, y) ) );
				y += p;
			}
			else
			{
				nro += ( upper_bound( o1.begin(), o1.end(), make_pair(x, y) ) - lower_bound( o1.begin(), o1.end(), make_pair(x, y - p) ) );
				y -= p;
			}
		}
	}
	
	fout << nro << '\n';
	
	fin.close();
	fout.close();
	return 0;
}

int BinarySearch1( vector<pair<int, int>> v, pair<int, int> val )
{
	int st = 0, dr = no, mid, poz = no + 1;
	
	while ( st <= dr )
	{
		mid = (st + dr) / 2;
		
		if ( v[mid] < val )
		{
			st = mid + 1;
		}
		else
		{
			dr = mid - 1;
			poz = mid;
		}
	}
	
	return poz;
}

int BinarySearch2( vector<pair<int, int>> v, pair<int, int> val )
{
	int st = 0, dr = no, mid, poz = no + 1;
	
	while ( st <= dr )
	{
		mid = (st + dr) / 2;
		
		if ( v[mid] <= val )
		{
			st = mid + 1;
		}
		else
		{
			dr = mid - 1;
			poz = mid;
		}
	}
	
	return poz;
}