Cod sursa(job #2640547)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 6 august 2020 19:46:44
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.28 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n, q;
vector<int> yforx[16100];
vector<pair<int, int> > ini_animals, animals;
set<int> ini_xes;
unordered_map<int, int> coresp_x;

void compress_xes();
int find_compressed_x_left(int x);
int find_compressed_x_right(int x);

struct aintx {
	int siz = 0, left = -1, right = -1;
	aintx *subaint[2];
	vector<int> ainty;
	vector<int> ys;
	set<int> ini_ys;
	unordered_map<int, int> coresp_y;

	int query(int nod, int st, int dr, int y_left, int y_right) {
		if (y_left <= st && dr <= y_right)
			return this->ainty[nod];

		int total = 0;
		int mij = (st + dr) / 2;

		if (y_left <= mij)
			total += query(2 * nod, st, mij, y_left, y_right);
		if (y_right > mij)
			total += query(2 * nod + 1, mij + 1, dr, y_left, y_right);

		return total;
	}

	void increase_y(int nod, int st, int dr, int y) {
		if (st == dr) {
			this->ainty[nod]++;
			return;
		}

		int mij = (st + dr) / 2;
		if (y <= mij)
			this->increase_y(2 * nod, st, mij, y);
		else
			this->increase_y(2 * nod + 1, mij + 1, dr, y);

		this->ainty[nod] = this->ainty[2 * nod] + this->ainty[2 * nod + 1];
	}

	void add_animal(int y) {
		this->increase_y(1, 1, this->siz, y);
	}

	int find_compressed_y_up(int y) {
		return this->coresp_y[*(--this->ini_ys.lower_bound(y + 1))];
	}

	int find_compressed_y_down(int y) {
		return this->coresp_y[*this->ini_ys.upper_bound(y - 1)];
	}

	void compress_ys() {
		for (int y : this->ys) /// NEED TO HAVE THE YS VECTOR
			ini_ys.insert(y);
		for (auto itr = this->ini_ys.begin(); itr != this->ini_ys.end(); itr++) {
			this->siz++;
			if (itr != this->ini_ys.begin()) {
				if (*itr == *(--itr))
					this->siz--;
				itr++;
			}
			this->coresp_y[*itr] = this->siz;
		}
	}

	aintx(int st, int dr) {
		this->left = st;
		this->right = dr;

		/// stocam toate y-urile care se gasesc pe fasiile cuprinse de subarbore
		for (int i = st; i <= dr; i++)
			for (int y : yforx[i])
				this->ys.push_back(y);

		/// compresam y-urile din subarborele curent
		this->compress_ys();

		/// formam ainty-ul cu y-urile compresate
		this->ainty.resize(4 * this->siz + 100);
		for (int y : this->ys)
			this->add_animal(this->coresp_y[y]);

		/// cream subarborii copii daca exista
		if (this->left != this->right) {
			int mij = (this->left + this->right) / 2;
			this->subaint[0] = new aintx(this->left, mij);
			this->subaint[1] = new aintx(mij + 1, this->right);
		}
	}

	int ask(int x1, int x2, int y1, int y2) {
		if (x1 <= this->left && this->right <= x2) {
			if (y1 > *this->ini_ys.rbegin() || y2 < *this->ini_ys.begin())
				return 0;

			y1 = this->find_compressed_y_down(y1);
			y2 = this->find_compressed_y_up(y2);

			return this->query(1, 1, this->siz, y1, y2);
		}

		int total = 0;
		if (x1 <= this->subaint[0]->right)
			total += this->subaint[0]->ask(x1, x2, y1, y2);
		if (x2 > this->subaint[0]->right)
			total += this->subaint[1]->ask(x1, x2, y1, y2);

		return total;
	}
} *root;

int main() {
	fin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		fin >> x >> y;
		ini_animals.emplace_back(x, y);
		animals.emplace_back(x, y);
	}

	compress_xes();

	for (pair<int, int> &animal : ini_animals)
		yforx[coresp_x[animal.first]].push_back(animal.second);

	root = new aintx(1, coresp_x[*ini_xes.rbegin()]);

	fin >> q;
	while (q--) {
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;

		if (x1 > *ini_xes.rbegin() || x2 < *ini_xes.begin()) {
			fout << 0 << '\n';
			continue;
		}

		x1 = find_compressed_x_left(x1);
		x2 = find_compressed_x_right(x2);

		fout << root->ask(x1, x2, y1, y2) << '\n';
	}
    return 0;
}

void compress_xes() {
	for (pair<int, int> animal : animals)
		ini_xes.insert(animal.first);

	int xmax = 0;
	for (auto itr = ini_xes.begin(); itr != ini_xes.end(); itr++) {
		xmax++;
		if (itr != ini_xes.begin()) {
			if (*itr == *(--itr))
				xmax--;
			itr++;
		}
		coresp_x[*itr] = xmax;
	}

	for (pair<int, int> &animal : animals)
		animal = make_pair(coresp_x[animal.first], animal.second);
}

int find_compressed_x_left(int x) {
	return coresp_x[*ini_xes.upper_bound(x - 1)];
}

int find_compressed_x_right(int x) {
	return coresp_x[*(--ini_xes.lower_bound(x + 1))];
}