Cod sursa(job #2912966)

Utilizator lolismekAlex Jerpelea lolismek Data 11 iulie 2022 20:09:34
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N = 16000;
struct point{
	int x, y;
}p[N + 1];

bool cmp(point a, point b){
	return a.x < b.x;
}

struct leaf{
	int n;
	vector <point> v;
}aint[4 * N + 1];

void build(int nod, int st, int dr){
	if(st == dr){
		aint[nod].n = 1;
		aint[nod].v.push_back(p[st]);
		return;
	}

	int mij = (st + dr) / 2;
	build(2 * nod, st, mij);
	build(2 * nod + 1, mij + 1, dr);

	aint[nod].n = aint[2 * nod].n + aint[2 * nod + 1].n;

	int i1 = 0, i2 = 0;
	while(i1 < (int)aint[2 * nod].v.size() && i2 < (int)aint[2 * nod + 1].v.size()){
		if(aint[2 * nod].v[i1].y < aint[2 * nod + 1].v[i2].y)
			aint[nod].v.push_back(aint[2 * nod].v[i1++]);
		else
			aint[nod].v.push_back(aint[2 * nod + 1].v[i2++]);
	}

	while(i1 < (int)aint[2 * nod].v.size())
		aint[nod].v.push_back(aint[2 * nod].v[i1++]);

	while(i2 < (int)aint[2 * nod + 1].v.size())
		aint[nod].v.push_back(aint[2 * nod + 1].v[i2++]);
}

int ans;
void query(int nod, int st, int dr, int Qst, int Qdr, int yMin, int yMax){

	if(Qst <= st && dr <= Qdr){
		int li = 0, ls = aint[nod].v.size() - 1, tmp = 0;
		while(li <= ls){
			int mij = (li + ls) / 2;

			if(aint[nod].v[mij].y < yMin)
				li = mij + 1, tmp = mij;
			else
				ls = mij - 1;
		}

		if(aint[nod].v[tmp].y < yMin)
			tmp++;

		ans -= tmp;

		li = 0, ls = aint[nod].v.size() - 1, tmp = 0;
		while(li <= ls){
			int mij = (li + ls) / 2;
			if(aint[nod].v[mij].y <= yMax)
				li = mij + 1, tmp = mij;
			else
				ls = mij - 1;
		}

		if(aint[nod].v[tmp].y <= yMax)
			tmp++;

		ans += tmp;

		return;
	}

	int mij = (st + dr) / 2;
	if(Qst <= mij)
		query(2 * nod, st, mij, Qst, Qdr, yMin, yMax);
	if(mij + 1 <= Qdr)
		query(2 * nod + 1, mij + 1, dr, Qst, Qdr, yMin, yMax);
}

int main(){

	int n;
	fin >> n;

	for(int i = 1; i <= n; i++)
		fin >> p[i].x >> p[i].y;
	sort(p + 1, p + n + 1, cmp);

	build(1, 1, n);

	int q;
	fin >> q;

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

		if(x2 < p[1].x || p[n].x < x1){
			fout << "0\n";
			continue;
		}

		ans = 0;

		int li = 1, ls = n, L = 1, R = n;
		while(li <= ls){
			int mij = (li + ls) / 2;
			if(p[mij].x < x1)
				li = mij + 1;
			else
				ls = mij - 1, L = mij;
		}

		li = 1, ls = n;
		while(li <= ls){
			int mij = (li + ls) / 2;
			if(p[mij].x <= x2)
				li = mij + 1, R = mij;
			else
				ls = mij - 1;
		}

		query(1, 1, n, L, R, y1, y2);

		fout << ans << '\n';
	}

	return 0;
}