Cod sursa(job #2908712)

Utilizator lolismekAlex Jerpelea lolismek Data 5 iunie 2022 11:26:52
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>

using namespace std;

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

const int N = 16000, M = 1e5, MAXY = 3e5;

struct punct{
	int x, y;
}v[N + 1];

struct dreptunghi{
	int x1, y1, x2, y2;
}d[M + 1];

struct query{
	int l, r, val, ind;
}q[2 * M + 1];

bool cmp1(punct a, punct b){
	return a.x < b.x;
}

/* ----------------------- AIB ------------------------ */

int aib[MAXY + 1];

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

void update(int poz, int val){
	for(int i = poz; i <= MAXY; i += lsb(i))
		aib[i] += val;
}

int query(int poz){
	int ans = 0;
	for(int i = poz; i >= 1; i -= lsb(i))
		ans += aib[i];
	return ans;
}

/* ---------------------------------------------------- */

struct upd{
	int val, ind, start;
};

/*
	start - 0 - incepe jos
	      - 1 - se termina jos
	      - 2 - incepe sus
	      - 3 - se termina sus
*/

vector <upd> lin[MAXY + 1];

struct for_ans{
	int sus, jos;
}ans[M + 1];

int main(){

	/* ---------------------- citire ---------------------- */

	int n;
	fin >> n;
	for(int i = 1; i <= n; i++)
		fin >> v[i].x >> v[i].y;

	int m;
	fin >> m;
	for(int i = 1; i <= m; i++)
		fin >> d[i].x1 >> d[i].y1 >> d[i].x2 >> d[i].y2;

	/* ---------------------------------------------------- */



	/* --------------- normalizare Y ---------------------- */

	vector <int> aux;
	for(int i = 1; i <= n; i++)
		aux.push_back(v[i].y);
	for(int i = 1; i <= m; i++)
		aux.push_back(d[i].y1), aux.push_back(d[i].y2);
	sort(aux.begin(), aux.end());

	int ct = 1;
	map <int, int> mp;
	for(int i = 0; i < (int)aux.size(); i++)
		if(mp.find(aux[i]) == mp.end())
			mp[aux[i]] = ct++;
	
	for(int i = 1; i <= n; i++)
		v[i].y = mp[v[i].y];
	for(int i = 1; i <= m; i++)
		d[i].y1 = mp[d[i].y1], d[i].y2 = mp[d[i].y2];

	/* ---------------------------------------------------- */



	/* -------------- stabilim queries -------------------- */

	sort(v + 1, v + n + 1, cmp1);

	for(int i = 1; i <= m; i++){
		int st, dr, ans;

		st = 1, dr = n, ans = 0;
		while(st <= dr){
			int mij = (st + dr) / 2;
			if(d[i].x1 < v[mij].x)
				st = mij + 1, ans = mij;
			else
				dr = mij - 1;
		}
		q[2 * i - 1].l = ans;
		q[2 * i].l = ans;

		st = 1, dr = n, ans = 0;
		while(st <= dr){
			int mij = (st + dr) / 2;
			if(d[i].x2 <= v[mij].x)
				st = mij + 1, ans = mij;
			else
				dr = mij - 1;
		}
		q[2 * i - 1].r = ans;
		q[2 * i].r = ans;

		q[2 * i - 1].val = d[i].y1;
		q[2 * i].val = d[i].y2;

		q[2 * i - 1].ind = i;
		q[2 * i].ind = i;

		lin[q[2 * i - 1].l].push_back({q[2 * i - 1].val, q[2 * i - 1].ind, 0});
		lin[q[2 * i - 1].r].push_back({q[2 * i - 1].val, q[2 * i - 1].ind, 1});
		lin[q[2 * i].l].push_back({q[2 * i].val, q[2 * i].ind, 2});
		lin[q[2 * i].r].push_back({q[2 * i].val, q[2 * i].ind, 3});

	}

	/* ---------------------------------------------------- */



	/* ------------------- parcurgere y ------------------- */

	for(int i = 1; i <= MAXY; i++){
		for(int j = 0; j < (int)lin[i].size(); j++){
			if(lin[i][j].start == 0){
				ans[lin[i][j].ind].jos -= query(lin[i][j].val - 1);
				update(lin[i][j].val, 1);
			}else if(lin[i][j].start == 1){
				ans[lin[i][j].ind].jos += query(lin[i][j].val - 1);
				update(lin[i][j].val, 1);
			}else if(lin[i][j].start == 2){
				ans[lin[i][j].ind].sus -= query(lin[i][j].val - 1);
				update(lin[i][j].val, 1);
			}else{
				ans[lin[i][j].ind].sus += query(lin[i][j].val - 1);
				update(lin[i][j].val, 1);
 			}
		}
	}

	/* ---------------------------------------------------- */



	/* ------------------------ ans ----------------------- */

	for(int i = 1; i <= m; i++)
		fout << ans[i].sus - ans[i].jos << '\n';

	/* ---------------------------------------------------- */

	return 0;
}