Cod sursa(job #2908615)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 4 iunie 2022 18:37:47
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>

using namespace std;

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

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

const int LEFT = 1;
const int POINT = 2;
const int RIGHT = 3;

struct Event {
	int TYPE;
	int x;
	int y1, y2;
	int index;
};

struct Point {
	int x, y;
};

struct Query {
	int x1, y1;
	int x2, y2;
};

vector<Event> Events;
vector<Point> Points;
vector<Query> 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 Fenwick {
	int N;
	vector<T> tree;

	Fenwick () {

	}

	Fenwick(int size) {
		N = size;
		tree = vector<T> (size);
	}

	Fenwick& operator = (const Fenwick &_) {
		N = _.N;
		tree = _.tree;
		return *this;
	}

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

	void update(int position, int value) {
		for(int i = position; i <= N; i += lsb(i)) {
			tree[i] += value;
		}
	}

	int query(int position) {
		int ret = 0;
		for(int i = position; i > 0; i -= lsb(i)) {
			ret += tree[i];
		}
		return ret;
	}

	int query(int left, int right) {
		return query(right) - query(left - 1);
	}
};

int N, M;
Fenwick<int> DS;

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

	fin >> M;
	Queries = vector<Query> (M);
	for(auto &q: Queries) {
		fin >> q.x1 >> q.y1 >> q.x2 >> q.y2;
	}

	for(const auto &p: Points) {
		values.push_back(p.y);
	}
	for(const auto &q: Queries) {
		values.push_back(q.y1);
		values.push_back(q.y2);
	}
	sort(values.begin(), values.end());
	for(auto &p: Points) {
		p.y = normalize(p.y);
	}
	for(auto &q: Queries) {
		q.y1 = normalize(q.y1);
		q.y2 = normalize(q.y2);
	}

	for(const auto &p: Points) {
		Events.push_back({POINT, p.x, 0, 0, p.y});
	}

	int index = 0;
	for(const auto &q: Queries) {
		Events.push_back({LEFT, q.x1, q.y1, q.y2, index});
		Events.push_back({RIGHT, q.x2, q.y1, q.y2, index});
		index++;
	}

	sort(Events.begin(), Events.end(), [] (const Event &a, const Event &b) {
		if(a.x == b.x) {
			return a.TYPE < b.TYPE;
		}
		return a.x < b.x;
	});

	answers = vector<int> (M);
	DS = Fenwick<int> (values.size() + 1);
	for(const auto &e: Events) {
		if(e.TYPE == POINT) {
			DS.update(e.index, 1);
		} else if(e.TYPE == LEFT) {
			answers[e.index] = -DS.query(e.y1, e.y2);
		} else {
			answers[e.index] += DS.query(e.y1, e.y2);
		}
	}

	for(const auto &a: answers) {
		fout << a << '\n';
	}
	return 0;
}