Cod sursa(job #2456098)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 13 septembrie 2019 17:40:39
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 16007;

vector <int> arb[DIM * 4];

struct Point
{
	int x, y;
	int pos;
};

bool cmp(Point a, Point b)
{
	if(a.x == b.x)
		return a.y < b.y;
	
	return a.x < b.x;
}

int p = 0;

vector <Point> v;

void build(int pos, int l, int r)
{
	if(l == r)
	{
		while(p < v.size() && v[p].pos == l)
		{
			arb[pos].push_back(v[p].y);
			p++;
		}
		
		return ;
	}
	
	int mid = (l + r) / 2;
	
	build(pos * 2, l, mid);
	build(pos * 2 + 1, mid + 1, r);
	
	int it = 0;
	
	for(auto i : arb[pos * 2])
	{
		while(it < arb[pos * 2 + 1].size() && arb[pos * 2 + 1][it] <= i)
		{
			arb[pos].push_back(arb[pos * 2 + 1][it]);
			it++;
		}
		
		arb[pos].push_back(i);
	}
	
	while(it < arb[pos * 2 + 1].size())
	{
		arb[pos].push_back(arb[pos * 2 + 1][it]);
		it++;
	}
}

int query(int pos, int l, int r, int x1, int y1, int x2, int y2)
{
	if(x1 <= l && r <= x2)
	{
		int lo = 0;
		int hi = arb[pos].size() - 1;
		
		int it1 = 0;
		int it2 = 0;
		
		while(lo <= hi)
		{
			int mid = (lo + hi) / 2;
			
			if(arb[pos][mid] < y1)
			{
				lo = mid + 1;
			}
			else
			{
				hi = mid - 1;
				it1 = mid;
			}
		}
		
		lo = 0;
		hi = arb[pos].size() - 1;
		
		while(lo <= hi)
		{
			int mid = (lo + hi) / 2;
			
			if(arb[pos][mid] > y2)
			{
				hi = mid - 1;
			}
			else
			{
				lo = mid + 1;
				it2 = mid;
			}
		}
		
		if(arb[pos][it1] > y2 || arb[pos][it2] < y1)
			return 0;
		
		return it2 - it1 + 1;
	}
	
	int mid = (l + r) / 2;
	
	int sum = 0;
	
	if(x1 <= mid)
		sum += query(pos * 2, l, mid, x1, y1, x2, y2);
	
	if(x2 > mid)
		sum += query(pos * 2 + 1, mid + 1, r, x1, y1, x2, y2);
	
	return sum;
}

main()
{
	int n;
	fin >> n;
	
	for(int i = 1; i <= n; i++)
	{
		int x, y;
		fin >> x >> y;
		
		v.push_back({x, y, 0});
	}
	
	sort(v.begin(), v.end(), cmp);
	
	v[0].pos = 1;
	
	int k = 1;
	
	for(int i = 1; i < v.size(); i++)
	{
		if(v[i].x != v[i - 1].x)
			k++;
		
		v[i].pos = k;
	}
	
	build(1, 1, k);
	
	fin >> n;
	
	while(n--)
	{
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;
		
		int l = 0;
		int r = v.size() - 1;
		
		int it1 = 0;
		int it2 = 0;
		
		while(l <= r)
		{
			int mid = (l + r) / 2;
			
			if(v[mid].x < x1)
			{
				l = mid + 1;
			}
			else
			{
				r = mid - 1;
				it1 = mid;
			}
		}
		
		l = 0;
		r = v.size() - 1;
		
		while(l <= r)
		{
			int mid = (l + r) / 2;
			
			if(v[mid].x > x2)
			{
				r = mid - 1;
			}
			else
			{
				l = mid + 1;
				it2 = mid;
			}
		}
		
		if(v[it1].x > x2 || v[it2].x < x1)
		{
			fout << 0 << '\n';
			continue;
		}
		
		x1 = v[it1].pos;
		x2 = v[it2].pos;
		
		int res = query(1, 1, k, x1, y1, x2, y2);
		
		fout << res << '\n';
	}
}