Cod sursa(job #1721084)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 24 iunie 2016 14:05:32
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
using namespace std;
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2000000010

class Query
{
private:
	vector< vector<int> > aint;
	int n, x1, x2, y1, y2;

	void build_aint(int, int, int, vector<pii>&);
	int query(int, int, int);

public:
	Query() {}
	void init(vector<pii>&);
	int getNr(int, int, int, int);
};

vector< int > X;
vector< pii > v;
Query query;

void read(ifstream&);

int main()
{
	int q, x1, x2, y1, y2;
	ifstream fin("zoo.in");
	ofstream fout("zoo.out");

	read(fin);
	query.init(v);

	for (fin >> q; q; --q)
	{
		fin >> x1 >> y1 >> x2 >> y2;

		if (x1 > X.back() || x2 < X.front())
		{
			fout << 0 << '\n';
		}
		else
		{
			x1 = lower_bound(X.begin(), X.end(), x1) - X.begin() + 1;
			x2 = upper_bound(X.begin(), X.end(), x2) - X.begin(); // + 1 - 1

			fout << query.getNr(x1, y1, x2, y2) << '\n';
		}
	}

	fin.close();
	fout.close();

    return 0;
}

void read(ifstream &fin)
{
	int i, n, x;

	fin >> n;
	v.resize(n);

	for (i = 0; i < n; ++i) fin >> v[i].first >> v[i].second, X.push_back(v[i].first);
	sort(v.begin(), v.end());

	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	for (x = 1, i = 0; i < n; ++i, ++x)
	{
		while (i + 1 < n && v[i].first == v[i + 1].first) v[i++].first = x;
		v[i].first = x;
	}
}

void Query::init(vector<pii> &v)
{
	n = v.back().first;
	aint.resize(4 * n);

	build_aint(1, 1, n, v);
}

int Query::getNr(int _x1, int _y1, int _x2, int _y2)
{
	x1 = _x1;
	y1 = _y1;
	x2 = _x2;
	y2 = _y2;

	return query(1, 1, n);
}

void Query::build_aint(int node, int l, int r, vector<pii> &v)
{
	if (l == r)
	{
		auto begin_it = lower_bound(v.begin(), v.end(), make_pair(l, -INF));
		auto end_it = lower_bound(v.begin(), v.end(), make_pair(l + 1, -INF));

		aint[node].reserve(end_it - begin_it);
		for (auto it = begin_it; it != end_it; ++it) aint[node].push_back(it->second);
	}
	else
	{
		int mid = (l + r) / 2;

		build_aint(2 * node, l, mid, v);
		build_aint(2 * node + 1, mid + 1, r, v);

		aint[node].resize(aint[2 * node].size() + aint[2 * node + 1].size());
		merge(aint[2 * node].begin(), aint[2 * node].end(), aint[2 * node + 1].begin(), aint[2 * node + 1].end(), aint[node].begin());
	}
}

int Query::query(int node, int l, int r)
{
	if (x1 <= l && r <= x2)
	{
		auto begin_it = lower_bound(aint[node].begin(), aint[node].end(), y1);
		auto end_it = upper_bound(aint[node].begin(), aint[node].end(), y2);

		return end_it - begin_it;
	}

	int mid = (l + r) / 2, v1, v2;

	v1 = (mid >= x1 ? query(2 * node, l, mid) : 0);
	v2 = (mid < x2 ? query(2 * node + 1, mid + 1, r) : 0);

	return v1 + v2;
}