Cod sursa(job #1809752)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 19 noiembrie 2016 11:14:03
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

typedef struct Nod * Arbore;
struct Nod
{
	int st, dr;
	Arbore left = 0, right = 0;
	int val = 0;
	Nod() { }
	Nod(Arbore x) : st(x->st), dr(x->dr), left(x->left), right(x->right), val(x->val) { }
};

Arbore make_Arb(int st, int dr);
void update(Arbore & n, int p);
int query(Arbore n, int st, int dr);
pair <pair <int, int>, pair <int, int>> drept(int x1, int y1, int x2, int y2);
void norm();

map <int, int> norm_x, norm_y;
pair <int, int> coord[20000];
vector <Arbore> timpi;
int n;
const int NMAX = 20000;

int main()
{
	ifstream in("zoo.in");

	in >> n;
	for (int i = 1; i <= n; i++)
		in >> coord[i].first >> coord[i].second;

	sort(coord + 1, coord + n + 1, [&] (pair <int, int> & x, pair <int, int> & y) { return x.second < y.second; });

	norm();

	coord[0] = { -2e9, -2e9 };
	norm_x[-2e9] = 0;
	norm_x[1e9] = NMAX - 1;

	timpi.push_back(make_Arb(0, NMAX));

	for (int i = 1; i <= n; i++) {
		timpi.push_back(timpi[i - 1]);
		update(timpi[i], norm_x[coord[i].first]);
	}

	int m, x1, y1, x2, y2;
	
	in >> m;
	ofstream out("zoo.out");

	while (m--) {
		in >> x1 >> y1 >> x2 >> y2;
		pair <pair <int, int>, pair <int, int>> c = drept(x1, y1, x2, y2);
		x1 = c.first.first, x2 = c.second.first;
		y1 = c.first.second, y2 = c.second.second;
		out << query(timpi[y2], x1, x2) - query(timpi[y1], x1, x2) << '\n';
	}

	return 0;
}


pair <pair <int, int>, pair <int, int>> drept(int x1, int y1, int x2, int y2)
{
	int x1f(0), x2f(0), y1f(0), y2f(0), q(0);

	q = 1 << 20;
	while (q > 0) {
		if (y1f + q <= n && coord[y1f + q].second < y1)
			y1f += q;
		q /= 2;
	}
	q = 1 << 20;
	while (q > 0) {
		if (y2f + q <= n && coord[y2f + q].second <= y2)
			y2f += q;
		q /= 2;
	}

	x1f = norm_x.lower_bound(x1)->second;
	x2f = norm_x.upper_bound(x2)->second;
	x2f--;

	return { { x1f, y1f }, { x2f, y2f } };
}

void norm()
{
	for (int i = 1; i <= n; i++) {
		norm_x[coord[i].first] = 0;
		norm_y[coord[i].second] = 0;
	}
	int c1 = 0, c2 = 0;
	
	for (auto & i : norm_x)
		i.second = ++c1;

	for (auto & i : norm_y)
		i.second = ++c2;
}


int query(Arbore n, int st, int dr)
{
	if (dr < n->st || st > n->dr)
		return 0;

	if (st <= n->st && dr >= n->dr)
		return n->val;

	return query(n->left, st, dr) + query(n->right, st, dr);
}

void update(Arbore & n, int p)
{
	if (p < n->st || p > n->dr)
		return;
	Arbore x = new Nod(n);
	n = x;

	n->val++;
	if (n->st != n->dr)
		update(n->left, p), update(n->right, p);
}

Arbore make_Arb(int st, int dr)
{
	Arbore n = new Nod();
	n->st = st, n->dr = dr;
	if (st != dr) {
		int mij = (st + dr) / 2;
		n->left = make_Arb(st, mij);
		n->right = make_Arb(mij + 1, dr);
	}
	return n;
}