Cod sursa(job #1074276)

Utilizator tudorv96Tudor Varan tudorv96 Data 7 ianuarie 2014 13:53:56
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

map <int, vector <pair <int, int> > > Mx, My;
int n, m, x, y;
vector <int> vx, vy;
long long sol;

long long BSx(int x, int lo, int hi) {
	int crt = -1;
	for (unsigned step = (1 << 17); step; step >>= 1)
		if (step + crt < Mx[x].size() && Mx[x][step + crt].second < lo)
			crt += step;
	long long sol = 0;
	int last = -1;
	for (unsigned i = crt + 1; i < Mx[x].size() && Mx[x][i].first <= hi; ++i)
		if (last == -1 || Mx[x][last].second <= Mx[x][i].first) {
			last = i;
			sol += min(Mx[x][i].second, hi) - max(Mx[x][i].first, lo) + 1;
		}
	return sol;
}

long long BSy(int y, int lo, int hi) {
	int crt = -1;
	for (unsigned step = (1 << 17); step; step >>= 1)
		if (step + crt < My[y].size() && My[y][step + crt].second < lo)
			crt += step;
	long long sol = 0;
	int last = -1;
	for (unsigned i = crt + 1; i < My[y].size() && My[y][i].first <= hi; ++i)
		if (last == -1 || My[y][last].second <= My[y][i].first) {
			last = i;
			sol += min(My[y][i].second, hi) - max(Mx[x][i].first, lo) + 1;
		}
	return sol;
}

bool cmp(pair <int, int> a, pair <int, int> b) {
	if (a.second != b.second)
		return a.first < b.first;
	return a.second < b.second;
}	

int main() {
	fin >> n >> m;
	while (n--) {
		int x, y;
		fin >> x >> y;
		Mx[x-2].push_back(make_pair (y, y));
		Mx[x-1].push_back(make_pair (y-1, y+1));
		Mx[x].push_back(make_pair (y-2, y+2));
		Mx[x+1].push_back(make_pair (y-1, y+1));
		Mx[x+2].push_back(make_pair (y, y));
		My[y-2].push_back(make_pair (x, x));
		My[y-1].push_back(make_pair (x-1, x+1));
		My[y].push_back(make_pair (x-2, x+2));
		My[y+1].push_back(make_pair (x-1, x+1));
		My[y+2].push_back(make_pair (x-2, x+2));
		vx.push_back (x);
		vy.push_back (y);
	}
	sort (vx.begin(), vx.end());
	sort (vy.begin(), vy.end());
	int last = -1;
	for (vector <int> :: iterator it = vx.begin(); it != vx.end(); ++it)
		if (last == -1 || vx[last] != *it) {
			sort (Mx[*it].begin(), Mx[*it].end(), cmp);
			last = it - vx.begin();
		}
	last = -1;
	for (vector <int> :: iterator it = vy.begin(); it != vy.end(); ++it)
		if (last == -1 || vy[last] != *it) {
			sort (My[*it].begin(), My[*it].end(), cmp);
			last = it - vy.begin();
		}
	while (m--) {
		char c;
		int d;
		fin >> c >> d;
		if (c == 'S') {
			sol += BSx (x, y - d, y); 
			y -= d;
		}
		if (c == 'N') {
			sol += BSx (x, y, y + d);
			y += d;
		}
		if (c == 'E') {
			sol += BSy (y, x, x + d);
			x += d;
		}
		if (c == 'V') {
			sol += BSy (y, x - d, x);
			x -= d;
		}
	}
	fout << sol;
}