Cod sursa(job #2249410)

Utilizator aurelionutAurel Popa aurelionut Data 29 septembrie 2018 19:50:27
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 16001;
int n, q;
int ans;
pair <int, int> v[NMAX];
int ox[NMAX];
vector <int> aint[4 * NMAX];

inline int LeftSon(const int &x)
{
	return 2 * x;
}

inline int RightSon(const int &x)
{
	return 2 * x + 1;
}

void Build(int node, int left, int right)
{
	if (left == right)
	{
		aint[node].push_back(v[left].second);
		return;
	}
	int mid = (left + right) / 2;
	Build(LeftSon(node), left, mid);
	Build(RightSon(node), mid + 1, right);
	aint[node].resize(aint[LeftSon(node)].size() + aint[RightSon(node)].size());
	merge(aint[LeftSon(node)].begin(), aint[LeftSon(node)].end(), aint[RightSon(node)].begin(), aint[RightSon(node)].end(), aint[node].begin());
}

void Query(int node, int left, int right, const int &LeftQuery, const int &RightQuery, int y1, int y2)
{
	if (LeftQuery <= left && right <= RightQuery)
	{
		ans += upper_bound(aint[node].begin(), aint[node].end(), y2) - lower_bound(aint[node].begin(), aint[node].end(), y1);
		return;
	}
	int mid = (left + right) / 2;
	if (LeftQuery <= mid)
		Query(LeftSon(node), left, mid, LeftQuery, RightQuery, y1, y2);
	if (RightQuery >= mid + 1)
		Query(RightSon(node), mid + 1, right, LeftQuery, RightQuery, y1, y2);
}

int main()
{
	FILE *fin = fopen("zoo.in", "r");
	FILE *fout = fopen("zoo.out", "w");
	fscanf(fin, "%d", &n);
	for (int i = 1;i <= n;++i)
		fscanf(fin, "%d %d", &v[i].first, &v[i].second);
	sort(v + 1, v + n + 1);
	for (int i = 1;i <= n;++i)
		ox[i] = v[i].first;
	Build(1, 1, n);
	int x1, y1, x2, y2;
	fscanf(fin, "%d", &q);
	for (int i = 1;i <= q;++i)
	{
		fscanf(fin, "%d %d %d %d", &x1, &y1, &x2, &y2);
		int ind1, ind2;
		ind1 = lower_bound(ox + 1, ox + n + 1, x1) - ox;
		ind2 = upper_bound(ox + 1, ox + n + 1, x2) - ox - 1;
		ans = 0;
		Query(1, 1, n, ind1, ind2, y1, y2);
		fprintf(fout, "%d\n", ans);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}