Cod sursa(job #3308941)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 30 august 2025 09:49:58
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX_N = 16000;

struct Point {
	int x, y;
	bool operator < (const Point &ob) const {
		if (x == ob.x)
			return y < ob.y;
		return x < ob.x;
	}
};

vector<int> st[(MAX_N << 2) | 1];
Point points[MAX_N + 1];
vector<int> vec[MAX_N + 1];
vector<int> coord;
int n, q;

void build(int node, int left, int right) {
	if (left == right) {
		st[node] = vec[left];
		sort(st[node].begin(), st[node].end());
		return;
	}
	int mid = left + ((right - left) >> 1);
	build(node << 1, left, mid);
	build(node << 1 | 1, mid + 1, right);
	merge(st[node << 1].begin(), st[node << 1].end(),
		  st[node << 1 | 1].begin(), st[node << 1 | 1].end(),
		  back_inserter(st[node]));
}

int query(int node, int left, int right, int x1, int y1, int x2, int y2) {
	if (x1 <= left && right <= x2)
		return upper_bound(st[node].begin(), st[node].end(), y2) - lower_bound(st[node].begin(), st[node].end(), y1);
	int mid = left + ((right - left) >> 1), res = 0;
	if (x1 <= mid)
		res += query(node << 1, left, mid, x1, y1, x2, y2);
	if (x2 > mid)
		res += query(node << 1 | 1, mid + 1, right, x1, y1, x2, y2);
	return res;
}

int main() {
	fin >> n;
	for (int i = 0; i < n; i++) {
		fin >> points[i].x >> points[i].y;
		coord.push_back(points[i].x);
	}
	
	sort(coord.begin(), coord.end());
	coord.erase(unique(coord.begin(), coord.end()), coord.end());
	
	for (int i = 0; i < n; i++) {
		points[i].x = lower_bound(coord.begin(), coord.end(), points[i].x) - coord.begin() + 1;
		vec[points[i].x].push_back(points[i].y);
	}
	
	build(1, 1, (int)coord.size());
	
	fin >> q;
	int x1, y1, x2, y2;
	while (q--) {
		fin >> x1 >> y1 >> x2 >> y2;
		x1 = lower_bound(coord.begin(), coord.end(), x1) - coord.begin() + 1;
		x2 = upper_bound(coord.begin(), coord.end(), x2) - coord.begin();
		if (x1 > x2)
			fout << "0\n";
		else
			fout << query(1, 1, (int)coord.size(), x1, y1, x2, y2) << "\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}