Cod sursa(job #3272225)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 28 ianuarie 2025 22:43:06
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

#define MAXN 16005

struct Node {
	int lfX, rgX;
	vector<int> y;
};

int n, m;
map<int, vector<int>> values;
vector<int> xcoords;

class SegmentTree {
public:
	vector<Node> m_tree;
	int m_size;

	SegmentTree(const vector<int>& xcoords,
							map<int, vector<int>>& values) {
		m_size = log2(xcoords.size());
		m_size += (1 << m_size) < xcoords.size();
		m_size = 1 << m_size;
		m_tree.resize(m_size * 2);
		Build(xcoords, values, 0, m_size - 1, 1);
	}

	int Query(int qLf, int qRg, int yLower, int yUpper, int lf, int rg, int node) {
		// cout << "START: " <<  m_tree[node].lfX << ' ' << m_tree[node].rgX << '\n';
		// cout << qLf << ' '<< qRg;
		if (m_tree[node].lfX >= qLf && m_tree[node].rgX <= qRg) {
			// cout << "BIN: " <<  BinSearchLowerBound(yLower, m_tree[node]) << ' ' << BinSearchUpperBound(yUpper, m_tree[node]) << '\n';
			return BinSearchUpperBound(yUpper, m_tree[node]) -
					BinSearchLowerBound(yLower, m_tree[node]) + 1;
		}

		// cout << "LF, RG: " << lf << ' ' << rg << '\n';
		// cout << m_tree[LfSon(node)].lfX << ' ' << m_tree[RgSon(node)].rgX << '\n';

		int mid = lf + (rg - lf) / 2;
		int ans = 0;
		if (m_tree[LfSon(node)].y.size() && qLf <= m_tree[LfSon(node)].rgX) {
			ans += Query(qLf, qRg, yLower, yUpper, lf, mid, LfSon(node));
		}
		if (m_tree[RgSon(node)].y.size() && qRg >= m_tree[RgSon(node)].lfX) {
			ans += Query(qLf, qRg, yLower, yUpper, mid + 1, rg, RgSon(node));
		}
		return ans;
	}

private:
	void Build(const vector<int>& xcoords,
						 map<int, vector<int>>& values,
						 int lf, int rg, int node) {
		if (lf == rg) {
			if (lf >= values.size()) {
				m_tree[node] = {xcoords[values.size() - 1], xcoords[values.size() - 1],
												{}};
				return;
			}
			m_tree[node] = {xcoords[lf], xcoords[lf], values[xcoords[lf]]};
			sort(m_tree[node].y.begin(), m_tree[node].y.end());
			return;
		}

		int mid = lf + (rg - lf) / 2;
		Build(xcoords, values, lf, mid, LfSon(node));
		Build(xcoords, values, mid + 1, rg, RgSon(node));
		Merge(m_tree[LfSon(node)], m_tree[RgSon(node)], m_tree[node]);
	}

	void Merge(const Node& lfNode, const Node& rgNode, Node& out) {
		out.lfX = lfNode.lfX;
		out.rgX = rgNode.rgX;
		out.y.resize(lfNode.y.size() + rgNode.y.size());

		int idxLf = 0;
		int idxRg = 0;
		for (int i = 0; i < out.y.size(); i++) {
			if (idxLf >= lfNode.y.size()) {
				out.y[i] = rgNode.y[idxRg++];
				continue;
			}
			if (idxRg >= rgNode.y.size()) {
				out.y[i] = lfNode.y[idxLf++];
				continue;
			}

			if (lfNode.y[idxLf] <= rgNode.y[idxRg]) {
				out.y[i] = lfNode.y[idxLf++];
			} else {
				out.y[i] = rgNode.y[idxRg++];
			}
		}
	}

	int BinSearchLowerBound(int bound, const Node& node) {
		int lf = 0;
		int rg = node.y.size() - 1;

		while (lf <= rg) {
			int mid = lf + (rg - lf) / 2;
			if (node.y[mid] >= bound) {
				rg = mid - 1;
			} else {
				lf = mid + 1;
			}
		}
		return lf; 
	}

	int BinSearchUpperBound(int bound, const Node& node) {
		int lf = 0;
		int rg = node.y.size() - 1;

		while (lf <= rg) {
			int mid = lf + (rg - lf) / 2;
			if (node.y[mid] <= bound) {
				lf = mid + 1;
			} else {
				rg = mid - 1;
			}
		}
		return rg; 
	}

	int LfSon(int node) {
		return node * 2;
	}

	int RgSon(int node) {
		return node * 2 + 1;
	}
}; // class SegmentTree

void ReadData() {
	fin >> n;
	
	int a, b;
	for (int i = 0; i < n; i++) {
		fin >> a >> b;
		values[a].push_back(b);
	}

	for (auto const& [key, value] : values) {
		xcoords.push_back({key});
	}

	fin >> m;
}

void Solve() {
	SegmentTree segTree = SegmentTree(xcoords, values);
	// for (Node& node : segTree.m_tree) {
	// 	cout << node.lfX << ' ' << node.rgX << ' ' << node.y.size() << '\n';
	// 	for (int y : node.y) {
	// 		cout << y << ' ';
	// 	}
	// 	cout << "\n\n";
	// }
	// cout << "\n\n";
	// cout << "\n\n";

	int Ax, Ay, Bx, By;
	for (int i = 0; i < m; i++) {
		fin >> Ax >> Ay >> Bx >> By;
		// cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
		fout << segTree.Query(Ax, Bx, Ay, By, 0, segTree.m_size - 1, 1) << '\n';
		// cout << "a" << '\n';
		// return;
		// if (i == 1) return;
	}
}

int main() {
	ReadData();
	Solve();
	return 0;
}