Cod sursa(job #253867)

Utilizator mariusdrgdragus marius mariusdrg Data 6 februarie 2009 13:06:45
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 1 Marime 3.06 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define pb push_back
#define mkp make_pair

using namespace std;

const int maxn = 200100;


vector<int> AIB[maxn],VAL[maxn],VECTV;
vector<pair<pair<int,int> ,int> > VECTEVEN;
vector<pair<int,int> > VECT;
int X[maxn],Y[maxn],R[maxn];
int N,M,ANS[maxn];


int cautare(vector<int> &vect,int val)
{
	unsigned int p = 0,x = 0;
	for(p = 1;p <= vect.size();p <<= 1);
	for(;p;p >>= 1)
		if (x + p < vect.size() && vect[x + p] <= val) x += p;
	return x;
}

inline int lsb(int x){return (x ^(x - 1)) & x;}

void update(vector<int> &aib,int poz,int val)
{
	unsigned int x = poz + 1;
	while(x <= aib.size())
	{
		aib[x - 1] += val;
		x += lsb(x);
	}
}

int querry(vector<int> &aib,int poz)
{
	poz++;
    if (aib.size() == 0) return 0;
	int cur = 0;
	while(poz)
	{
		cur += aib[poz - 1];
		poz -= lsb(poz);
	}
	return cur;
}

void solve(int aux1,int aux2,int aux3)
{
	for(unsigned int i = 0;i < VECTV.size();++i) {AIB[i].clear();VAL[i].clear();}
	VECTV.clear();
        VECTEVEN.clear();
	VECTV.pb(1000000000);
	VECTV.pb(-1000000000);
	for(int i = 1;i <= M; ++i)
	{
		VECTV.pb(X[i] + Y[i] - R[i]);	
	}
	sort(VECTV.begin(),VECTV.end());
	VECTV.resize(unique(VECTV.begin(),VECTV.end()) - VECTV.begin());
	for(int i = 1;i <= M; ++i)
		VECTEVEN.pb(mkp(mkp(X[i] * 2 + aux1,Y[i]),i));
	for(int i = 1;i <= N; ++i)
		VECTEVEN.pb(mkp(mkp(VECT[i].first * 2 + aux2 ,VECT[i].second),0));
	for(int i = 1;i <= N; ++i)
	{
		int val = VECT[i].first + VECT[i].second;
		int poz = cautare(VECTV,val);
		if (VECTV[poz] != val) continue;
		VAL[poz].pb(VECT[i].second);
		AIB[poz].pb(0);
	}
	for(unsigned int i = 0;i < VECTV.size(); ++i)
	{
		sort(VAL[i].begin(),VAL[i].end());
		VAL[i].resize(unique(VAL[i].begin(),VAL[i].end()) - VAL[i].begin());
		AIB[i].resize(VAL[i].size());
	}
	sort(VECTEVEN.begin(),VECTEVEN.end());
	for(unsigned int i = 0;i < VECTEVEN.size(); ++i)
	{

		int x = VECTEVEN[i].first.first;
                if (x % 2 != 0) x -= 1;
                x /= 2;
                int y = VECTEVEN[i].first.second;
                int poz = VECTEVEN[i].second;
		if (poz == 0)
		{
			int val = x + y;
			int pozn = cautare(VECTV,val);
			if (VECTV[pozn] != val) continue;
			update(AIB[pozn],cautare(VAL[pozn],y),1);	
		}
		else
		{
			int val = X[poz] + Y[poz] - R[poz];
			int pozn = cautare(VECTV,val);
			ANS[poz] += querry(AIB[pozn],cautare(VAL[pozn],y - aux3));
		}
	}
	return ;
}

int main()
{
	freopen("grendizer.in","r",stdin);
	freopen("grendizer.out","w",stdout);
	scanf("%d %d\n",&N,&M);
        VECT.pb(mkp(0,0));
	for(int i = 1;i <= N; ++i)
	{
		int x = 0,y = 0;
		scanf("%d %d\n",&x,&y);
		VECT.pb(mkp(x,y));
	}
	for(int i = 1;i <= M; ++i)
	{
		scanf("%d %d %d\n",&X[i],&Y[i],&R[i]);
	}
	solve(1,0,1);
	for(int i = 1;i <= N; ++i)	VECT[i].first *= -1;
	for(int i = 1;i <= M; ++i)	X[i] *= -1;

	solve(0,1,0);

	for(int i = 1;i <= N; ++i) VECT[i].second *= -1;
	for(int i = 1;i <= M; ++i) Y[i] *= -1;
	solve(1,0,1);
	for(int i = 1;i <= N; ++i)  VECT[i].first *= -1;
	for(int i = 1;i <= M; ++i)  X[i] *= -1;
	solve(0,1,0);
	for(int i = 1;i <= M; ++i) printf("%d\n",ANS[i]);
	return 0;
}