Cod sursa(job #2916358)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 29 iulie 2022 15:07:48
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

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

struct Point {
	int x, y;
};

vector<Point> Points, Queries;
vector<int> values;
vector<int> answers;

int normalize(int value) {
	return distance(values.begin(), lower_bound(values.begin(), values.end(), value)) + 1;
}

template <typename T>
struct implicitFenwickTree {
	int N;
	vector<vector<T>> tree;

	implicitFenwickTree () {

	}

	implicitFenwickTree(int size) {
		N = size;
		tree = vector<vector<T>> (size + 1);
	}

	implicitFenwickTree& operator = (const implicitFenwickTree &DS) {
		N = DS.N;
		tree = DS.tree;
		return *this;
	}

	int lsb(int i) {
		return i & (-i);
	}

	void insert(int x, int y) {
		for(int i = x; i <= N; i += lsb(i)) {
			tree[i].push_back(y);
		}
	}

	void sortAll() {
		for(int i = 1; i <= N; i++) {
			sort(tree[i].begin(), tree[i].end());
		}
	}

	int query(int x, int y) {
		int ret = 0;
		for(int i = x; i > 0; i -= lsb(i)) {
			ret += distance(tree[i].begin(), lower_bound(tree[i].begin(), tree[i].end(), y + 1));
		}
		return ret;
	}
};

int N, M;
implicitFenwickTree<int> DS;

int main() {
	fin >> N;
	Points = vector<Point> (N);
	for(auto &p: Points) {
		fin >> p.x >> p.y;
	}

	fin >> M;
	for(int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;

		Queries.push_back({x2, y2});
		Queries.push_back({x1 - 1, y2});
		Queries.push_back({x2, y1 - 1});
		Queries.push_back({x1 - 1, y1 - 1});
	}

	for(const auto &p: Points) {
		values.push_back(p.x);
	}
	for(const auto &q: Queries) {
		values.push_back(q.x);
	}

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

	for(auto &p: Points) {
		p.x = normalize(p.x);
	}
	for(auto &q: Queries) {
		q.x = normalize(q.x);
	}

	DS = implicitFenwickTree<int> (values.size());

	for(const auto &p: Points) {
		DS.insert(p.x, p.y);
	}

	DS.sortAll();

	for(int i = 0; i < (int) Queries.size(); i += 4) {
		int a = DS.query(Queries[i].x, Queries[i].y);
		int b = DS.query(Queries[i + 1].x, Queries[i + 1].y);
		int c = DS.query(Queries[i + 2].x, Queries[i + 2].y);
		int d = DS.query(Queries[i + 3].x, Queries[i + 3].y);

		fout << a - b - c + d << '\n';
	}
	return 0;
}