Cod sursa(job #498844)

Utilizator darrenRares Buhai darren Data 7 noiembrie 2010 13:46:46
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.82 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

void make_arrays();
bool mycrt1(const pair<int, int>& p1, const pair<int, int>& p2)
{
	if (p1.first != p2.first)
		return p1.first <= p2.first;
	return p1.second <= p2.second;
}
bool mycrt2(const pair<int, int>& p1, const pair<int, int>& p2)
{
	if (p1.second != p2.second)
		return p1.second <= p2.second;
	return p1.first <= p2.first;
}

int N, M;
vector<pair<int, int> > S1, S2;
int tot;

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

	fin >> N >> M;
	for (int i = 1, c1, c2; i <= N; ++i)
	{
		fin >> c1 >> c2;

		int aux = 0, chg = 0;
		for (int j = c1 - 2; j <= c1 + 2; ++j)
		{
			for (int k = c2 - aux; k <= c2 + aux; ++k)
				if (!(j == 0 && k == 0))
					S1.push_back(make_pair(j, k));

			if (chg == 0) ++aux;
			else          --aux;
			if (aux == 2) chg = true;
		}
	}

	make_arrays();

	char ch;
	int dm;
	int posx = 0, posy = 0;

	int rstep;
	for (rstep = 1; (rstep << 1) <= S1.size(); rstep <<= 1);

	for (int i = 1; i <= M; ++i)
	{
		fin >> ch >> dm;

		int step, j1, j2;

		switch (ch)
		{
			case 'N':
				step = rstep;
				for (j1 = -1; step; step >>= 1)
					if (j1 + step < S1.size())
					{
						if (S1[j1 + step].first < posx)
							j1 += step;
						else if (S1[j1 + step].first == posx && S1[j1 + step].second < posy)
							j1 += step;
					}
				step = rstep;
				for (j2 = -1; step; step >>= 1)
					if (j2 + step < S1.size())
					{
						if (S1[j2 + step].first < posx)
							j2 += step;
						else if (S1[j2 + step].first == posx && S1[j2 + step].second <= posy + dm)
							j2 += step;
					}
     			tot += j2 - j1;

				posy += dm;

				break;
			case 'S':
				step = rstep;
				for (j1 = -1; step; step >>= 1)
					if (j1 + step < S1.size())
					{
						if (S1[j1 + step].first < posx)
							j1 += step;
						else if (S1[j1 + step].first == posx && S1[j1 + step].second < posy - dm)
							j1 += step;
					}
				step = rstep;
				for (j2 = -1; step; step >>= 1)
					if (j2 + step < S1.size())
					{
						if (S1[j2 + step].first < posx)
							j2 += step;
						else if (S1[j2 + step].first == posx && S1[j2 + step].second <= posy)
							j2 += step;
					}
				tot += j2 - j1;

				posy -= dm;

				break;
			case 'E':
				step = rstep;
				for (j1 = -1; step; step >>= 1)
					if (j1 + step < S2.size())
					{
						if (S2[j1 + step].second < posy)
							j1 += step;
						else if (S2[j1 + step].second == posy && S2[j1 + step].first < posx)
							j1 += step;
					}
				step = rstep;
				for (j2 = -1; step; step >>= 1)
					if (j2 + step < S2.size())
					{
						if (S2[j2 + step].second < posy)
							j2 += step;
						else if (S2[j2 + step].second == posy && S2[j2 + step].first <= posx + dm)
							j2 += step;
					}
				tot += j2 - j1;

				posx += dm;

				break;
			case 'V':
				step = rstep;
				for (j1 = -1; step; step >>= 1)
					if (j1 + step < S2.size())
					{
						if (S2[j1 + step].second < posy)
							j1 += step;
						else if (S2[j1 + step].second == posy && S2[j1 + step].first < posx - dm)
							j1 += step;
					}
				step = rstep;
				for (j2 = -1; step; step >>= 1)
					if (j2 + step < S2.size())
					{
						if (S2[j2 + step].second < posy)
							j2 += step;
						else if (S2[j2 + step].second == posy && S2[j2 + step].first <= posx)
							j2 += step;
					}
				tot += j2 - j1;

				posx -= dm;

				break;
		}
	}

	fout << tot;

	fin.close();
	fout.close();
}

void make_arrays()
{
	S2 = S1;
	sort(S1.begin(), S1.end(), mycrt1);
	sort(S2.begin(), S2.end(), mycrt2);

	vector<pair<int, int> >::iterator it;

	it = unique(S1.begin(), S1.end());
	S1.resize(it - S1.begin());

	it = unique(S2.begin(), S2.end());
	S2.resize(it - S2.begin());
}