Cod sursa(job #516206)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 23 decembrie 2010 13:16:00
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 16010

pair <int, int> v[NMAX];
int n, m, logn;
int t[16][NMAX], sol;
int pct[NMAX], k;
int x1, y1, x2, y2;
int comp(const pair<int, int> &a, const pair<int, int> &b){
	if(a.first == b.first) return a.second < b.second;
	return a.first < b.first;
}
void normalizare(){
	sort(pct + 1, pct + k + 1);
	int newk = 1;
	for(int i = 2; i <= k; ++i)
		if(pct[i] != pct[i-1]) pct[++newk] = pct[i];
	k = newk;
}
inline int coord(int x, int ok, int v[],int p, int q){
	int i = p-1, step = 0;
	for(; (1<<step) <= (q-p+1); step++); step--;
	for(int j = step; j >= 0; --j)
		if(i + (1<<j) <= q && v[i + (1<<j)] < x) i += (1<<j);
	if(ok && i < q) return i+1;
	if(ok) return i;
	if(v[i+1] == x) return i+1;
	return i;
}
void new_cord(){
	for(; (1<<logn) <= n; ++logn); logn--;
	for(int i = 1; i <= n; ++i)
		v[i].first = coord(v[i].first, 1,pct,1,k), v[i].second = coord(v[i].second, 1,pct,1,k);
	sort(v + 1, v + n + 1, comp);
}
int cautbin(int x, int v[], int p, int q, int ok){
	int i = p-1;
	int step = 0;
	for(; (1<<step) <= (q-p+1); step++); step--;
	for(int j = step; j >= 0; --j)
		if(i + (1<<j) <= q && v[i+(1<<j)] - ok < x) i += (1<<j);
	return min(i + (ok^1), q);
}
void query_nod(int p, int q, int b){
	int p2 = cautbin(y2, t[b], p, q, 1);
	int p1 = cautbin(y1, t[b], p, q, 0);
	sol += p2-p1+1;
}
void query(int p, int q , int b){
	if(x1 <= p && q <= x2){
		query_nod(p,q,b);
		return;
	}
	int m = (p+q)/2;
	if(x1 <= m) query(p,m,b+1);
	if(x2 > m) query(m+1, q, b+1);
}
void update(int p, int q, int b){
	if(p == q){
		t[b][p] = v[p].second;
		return ;
	}
	int m = (p+q)/2;
	
	update(p, m, b+1);
	update(m+1,q, b+1);
	
	int i1 = p, i2 = m+1;
	for(int i = p; i <= q; ++i){
		if(i1 <= m && i2 <= q){
			if(t[b+1][i1] < t[b+1][i2]) t[b][i] = t[b+1][i1], i1++;
			else t[b][i] = t[b+1][i2], i2++;
		}
		else if(i1 <= m) t[b][i] = t[b+1][i1],i1++;
		else t[b][i] = t[b+1][i2], i2++;
	}
}
inline int poz(int x, int ok){
	int i = 0;
	for(int j = logn; j >= 0; --j)
		if(i + (1<<j) <= n && v[i+(1<<j)].first - ok < x) i += (1<<j);
	return i + (ok^1);
}
int main(){
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		int x, y;
		scanf("%d%d", &x, &y);
		pct[++k] = x; pct[++k] = y;
		v[i].first = x; v[i].second = y;
	}
	normalizare();
	new_cord();
	update(1, n, 0);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		x1 = coord(x1,1,pct,1,k); y1 = coord(y1,1,pct,1,k); 
		x2 = coord(x2,0,pct,1,k); y2 = coord(y2,0,pct,1,k);
		x1 = poz(x1, 0); x2 = poz(x2, 1);
		sol = 0;
		query(1, n, 0);
		printf("%d\n", sol);
	}
	return 0;
}