Cod sursa(job #582601)

Utilizator ProtomanAndrei Purice Protoman Data 15 aprilie 2011 16:40:17
Problema Grendizer Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <map>

#define MAX 100010
#define pb push_back

using namespace std;

int n, m;
int x[MAX], y[MAX];
vector <int> vert, oriz;
map <int, int> locVert, locOriz;
vector <int> vctEl[2][MAX];

inline int cautaBin(int m, int p, int fr, int ls, int key)
{
	if (fr > ls)
		return ls;
	int med = (fr + ls) / 2;
	
	if (vctEl[m][p][med] <= key)
		return cautaBin(m, p, med + 1, ls, key);
	else return cautaBin(m, p, fr, med - 1, key);
}

int main()
{
	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &x[i], &y[i]);

		vert.pb(x[i] + y[i]);
		oriz.pb(x[i] - y[i]);
	}

	sort(vert.begin(), vert.end());
	sort(oriz.begin(), oriz.end());

	for (int i = 1; i <= n; i++)
	{
		vctEl[0][i].pb(-LONG_MAX);
		vctEl[1][i].pb(-LONG_MAX);
		locVert[vert[i - 1]] = i;
		locOriz[oriz[i - 1]] = i;
	}

	for (int i = 1; i <= n; i++)
	{
		int l1 = locVert[x[i] + y[i]], l2 = locOriz[x[i] - y[i]];
		vctEl[0][l1].pb(y[i]);
		vctEl[1][l2].pb(y[i]);
	}

	for (int i = 1; i < n - 1; i++)
	{
		if (vert[i - 1] != vert[i])
			sort(vctEl[0][i].begin(), vctEl[0][i].end());
		if (oriz[i - 1] != oriz[i])
			sort(vctEl[1][i].begin(), vctEl[1][i].end());
	}
	sort(vctEl[0][n].begin(), vctEl[0][n].end());
	sort(vctEl[1][n].begin(), vctEl[1][n].end());

	for (int i = 1; i <= m; i++)
	{
		int x, y, r, sol = 0, p;
		scanf("%d %d %d", &x, &y, &r);

		p = locOriz[x - (y + r)];
		if (p)
			sol += cautaBin(1, p, 0, vctEl[1][p].size() - 1, y + r) - cautaBin(1, p, 0, vctEl[1][p].size() - 1, y);
		p = locOriz[x - (y - r)];
		if (p)
			sol += cautaBin(1, p, 0, vctEl[1][p].size() - 1, y) - cautaBin(1, p, 0, vctEl[1][p].size() - 1, y - r);
		p = locVert[x + (y + r)];
		if (p)
			sol += cautaBin(0, p, 0, vctEl[0][p].size() - 1, y + r - 1) - cautaBin(0, p, 0, vctEl[0][p].size() - 1, y);
		p = locVert[x + (y - r)];
		if (p)
			sol += cautaBin(0, p, 0, vctEl[0][p].size() - 1, y) - cautaBin(0, p, 0, vctEl[0][p].size() - 1, y - r - 1);

		printf("%d\n", sol);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}