Cod sursa(job #2774456)

Utilizator bubblegumixUdrea Robert bubblegumix Data 11 septembrie 2021 17:50:35
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 16005
#define all(v) v.begin(),v.end()
using namespace std;
vector<int> tree[4 * nmax];
vector<pair<int, int>> animale;
vector<int> aux[nmax];
vector<int> coord_x;
int n, m;

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

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 = dr + 1;
	while (st <= dr)
	{
		int mid = (st + dr) / 2;
		if (a[mid] <= x)
		{
			st = mid + 1;
		}
		else
		{
			ans = mid;
			dr = mid - 1;
		}
	}
	return ans;
}
void buildTree(int i, int l, int r)
{
	if (l == r)
	{
		tree[i].push_back(animale[l-1].second);
		return;
	}
	int m = (l + r) / 2;
	buildTree(i << 1, l, m);
	buildTree(i << 1 | 1, m + 1, r);
	merge(all(tree[i << 1]), all(tree[i << 1 | 1]), back_inserter(tree[i]));
}
int query(int i, int l, int r, int ql, int qr, int y1, int y2)
{
	if (l > qr || r<ql || l>r)
		return 0;
	if (l >= ql && r <= qr)
	{
		int a, b;
		a = minval(0, tree[i].size() - 1, y1, tree[i]);
		b = maxval(0, tree[i].size() - 1, y2, tree[i]);
		return b - a - 1;
	}
	int m = (l + r) / 2;
	return query(i << 1, l, m, ql, qr, y1, y2) +
		   query(i << 1|1, m+1, r, ql, qr, y1, y2);
}

int main()
{
	f >> n;
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		f >> a >> b;
		animale.push_back({ a,b });
	}
	sort(all(animale), [](pair<int, int> a, pair<int, int> b)
		{
			if (a.first == b.first)
				return a.second < b.second;
			return a.first < b.first;
		});
	for (auto it : animale)
		coord_x.push_back(it.first);
	
	buildTree(1, 1, n);
	f >> m;
	while (m--)
	{
		int x1, y1, x2, y2;
		f >> x1 >> y1 >> x2 >> y2;
		int l = minval(0, n - 1, x1, coord_x)+2;
		int r = maxval(0, n - 1, x2, coord_x);
		if (l <= r)
			g << query(1, 1, n, l, r, y1, y2)<<'\n';
		else
			g << 0 << '\n';
	}

}