Cod sursa(job #742717)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 1 mai 2012 09:32:14
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
struct punct {
	int x,y;
};
vector <int> a[100000];
punct v[16001];
int vx[16001];
int n,y1,y2,x1,x2,val,poz;
#define DIM 10000
char buff[10000];
void citire(int &numar)
{
	numar=0;
	char semn='+';     
	while (buff[poz]<'0'||buff[poz]>'9') {     
		semn=buff[poz];
		if(++poz==DIM) 
			fread(buff,1,DIM,stdin),poz=0;
	}          
	while ('0'<=buff[poz]&&buff[poz]<='9') {
		numar=numar*10+buff[poz]-'0';
		if (++poz==DIM) 
			fread(buff,1,DIM,stdin),poz=0;               
	}     
	if (semn=='-')
		numar=-numar;
}
inline bool cmp(const punct &a, const punct &b)
{
	return a.x<b.x;
}
void construieste(int nod, int st, int dr)
{
	int mij,i,j,n,m;
	if(st==dr) {
		a[nod].push_back(v[st].y);
		return ;
	}
	mij=(st+dr)/2;
	construieste(nod*2,st,mij);
	construieste(nod*2+1,mij+1,dr);
	n=a[nod*2].size()-1;
	m=a[nod*2+1].size()-1;
	i=0;
	j=0;
	while((i<=n)&&(j<=m)) {
		if(a[nod*2][i]<a[nod*2+1][j]) {
			a[nod].push_back(a[nod*2][i]);
			i++;
		}
		else if(a[nod*2][i]>=a[nod*2+1][j]) {
			a[nod].push_back(a[nod*2+1][j]);
			j++;
		}
	}
	for( ;i<=n;i++)
		a[nod].push_back(a[nod*2][i]);
	for( ;j<=m;j++)
		a[nod].push_back(a[nod*2+1][j]);
}
void query(int nod, int st, int dr)
{
	int mij;
	if((x1<=st)&&(dr<=x2)) {
		int x,y;
		if(a[nod][0]>=y1)
			x=0;
		else x=upper_bound(a[nod].begin(),a[nod].end(),y1-1)-a[nod].begin();
		if(a[nod][a[nod].size()-1]<=y2)
			y=a[nod].size()-1;
		else y=lower_bound(a[nod].begin(),a[nod].end(),y2+1)-a[nod].begin()-1;
		val=val+y-x+1;
		return;
	}
	mij=(st+dr)/2;
	if(x1<=mij)
		query(nod*2,st,mij);
	if(mij<x2)
		query(nod*2+1,mij+1,dr);
}
int main ()
{
	int i,m,aa,bb;
	freopen("zoo.in","r",stdin);
	ofstream g("zoo.out");
	citire(n);
	for(i=1;i<=n;i++) {
		citire(v[i].x);
		citire(v[i].y);
	}
	sort(v+1,v+n+1,cmp);
	construieste(1,1,n);
	for(i=1;i<=n;i++)
		vx[i]=v[i].x;
	citire(m);
	for(i=1;i<=m;i++) {
		citire(aa);
		citire(y1);
		citire(bb);
		citire(y2);
		if(v[1].x>=aa)
			x1=1;
		else x1=upper_bound(vx+1,vx+n+1,aa-1)-vx;
		if(v[n].x<=bb)
			x2=n;
		else x2=lower_bound(vx+1,vx+n+1,bb+1)-vx-1;
		val=0;
		if((x1<=x2)&&(y1<=y2)) 
			query(1,1,n);
		g<<val<<'\n';
	}
	g.close();
	return 0;
}