Cod sursa(job #2657153)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 9 octombrie 2020 20:27:52
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("zoo.in");
ofstream out("zoo.out");

vector<int> arb[65000],v;
vector<pair<int,int>> animale;

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

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

void build(int nod,int st,int dr)
{
	if(st==dr)
	{
		arb[nod].push_back(animale[st-1].second);
		return;
	}
	int mid=(st+dr)/2;
	build(nod*2,st,mid);
	build(nod*2+1,mid+1,dr);
	interclasare(nod,nod*2,nod*2+1);
}


int minval(int st,int dr,const int x,vector <int> &a)
{
	int ans=-1;
	while(st<=dr)
	{
		int mid=(st+dr)/2;
		if(a[mid]>=x)
			dr=mid-1;
		else 
		{
			ans=mid;
			st=mid+1;
		}
	}
	return ans;
}


int maxval(int st,int dr,const int x,vector <int> &a)
{
	int ans=-1;
	while(st<=dr)
	{
		int mid=(st+dr)/2;
		if(a[mid]<=x)
		{
			st=mid+1;
		}
		else 
		{
			ans=mid;
			dr=mid-1;
		}
	}
	return ans;
}


int query(int nod,int st,int dr,const int a,const int b,const int minn,const int maxx)
{
	if(a<=st && dr<=b)
	{
		int k=minval(0,arb[nod].size()-1,minn,arb[nod]);
		int z=maxval(0,arb[nod].size()-1,maxx,arb[nod]);
		int ans=z-(k+1);
		return ans;
	}
	int mid=(st+dr)/2;
	int ans=0;
	if(a<=mid)
	{
		ans+=query(nod*2,st,mid,a,b,minn,maxx);
	}
	if(b>mid)
	{
		ans+=query(nod*2+1,mid+1,dr,a,b,minn,maxx);
	}
	return ans;
}


int main()
{
	int n,m;
	in>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		in>>a>>b;
		animale.push_back({a,b});
	}
	sort(animale.begin(),animale.end(),ok);
	for(auto x:animale)
		v.push_back(x.first);
	build(1,1,n);
	in>>m;
	while(m--)
	{
		int x1,y1,x2,y2;
		in>>x1>>y1>>x2>>y2;
		int minn=minval(0,v.size()-1,x1,v)+2;
		int maxx=maxval(0,v.size()-1,x2,v);

		if(minn>maxx)
			out<<"0"<<"\n";
		else
			out<<query(1,1,n,minn,maxx,y1,y2)<<"\n";
	}
	return 0;
}