Cod sursa(job #833158)

Utilizator IoannaPandele Ioana Ioanna Data 11 decembrie 2012 23:02:06
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <vector>
#define NMAX (1<<20)
using namespace std;

int n,m,nr,p;
struct punct
{
	int x,y;
};
punct a[16010],c1,c2;

vector <int> v[NMAX];

ifstream in("zoo.in");
ofstream out("zoo.out");
	
void scan()
{
	in>>n;
	for (int i=1;i<=n;i++)
	{
		in>>a[i].x>>a[i].y;
	}
	in>>m;
}

int part(int st, int dr)
{
	punct p,aux;
	int i,j;
	i=st-1;
	j=dr+1;
	p=a[(st+dr)/2];
	while (1)
	{
		do{i++;}while (a[i].x<p.x || (a[i].x==p.x && a[i].y<p.y));
		do{j--;}while (p.x<a[j].x || (a[j].x==p.x && p.y<a[j].y));
		if (i<j)
		{
			aux=a[i];
			a[i]=a[j];
			a[j]=aux;
		}
		else return j;
	}
}


void quicks(int st,int dr)
{
	int p;
	if (st<dr)
	{
		p=part(st,dr);
		quicks(st,p); 
		quicks(p+1,dr);
	}
}

void merge(int k,int a,int b)
{
	int i=0,j=0;
	while (i<v[a].size() && j<v[b].size())
	{
		if (v[a][i]<v[b][j])
		{
			v[k].push_back(v[a][i]);			
			i++;
		}
		else 
		{
			v[k].push_back(v[b][j]);
			j++;
		}		
	}
	while (i<v[a].size())
	{
		v[k].push_back(v[a][i]);
		i++;
	}
	while (j<v[b].size())
	{
		v[k].push_back(v[b][j]);
		j++;
	}
}

void constructTree(int k,int st,int dr)
{
	if (st==dr)
	{
		while (p<=n && a[p].x==a[st].x)
		{
			v[k].push_back(a[p].y);
			p++;
		}
		return;
	}
	int mij;
	mij=(st+dr)/2;
	constructTree(2*k,st,mij);
	constructTree(2*k+1,mij+1,dr);
	merge(k,2*k,2*k+1);	
}

int cautbin(int k,int val)
{
	int i, step;
    for (step = 1; step < v[k].size(); step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < v[k].size()&& v[k][i + step] < val)
           i += step;
    return i;
}

void query(int k,int st,int dr)
{
	int k1,k2;
	if (st>dr || dr<st)
		return;
	if (c1.x<=a[st].x && a[dr].x<=c2.x)
	{
		k1=cautbin(k,c1.y);
		k2=cautbin(k,c2.y+1);
		nr=nr+k2-k1+1;
		return;
	}
	int mij;
	mij=(st+dr)/2;
	if (c1.x<=a[mij].x)
		query(2*k,st,mij);
	if (a[mij].x<c2.x)
		query(2*k+1,mij+1,dr);
}

void solve()
{
	for (int i=1;i<=m;i++)
	{
		nr=0;
		in>>c1.x>>c1.y>>c2.x>>c2.y;
		query(1,1,n);
		out<<nr<<"\n";
	}		
}

int main()
{
	p=1;
	scan();
	quicks(1,n);
	constructTree(1,1,n);
	solve();
	return 0;
}