Cod sursa(job #516223)

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

pair <int, int> v[NMAX];
int n, m, logn;
int t[16][NMAX], sol;
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;
}
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 i;
}
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;
}
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++];
			else t[b][i] = t[b+1][i2++];
		}
		else if(i1 <= m) t[b][i] = t[b+1][i1++];
		else t[b][i] = t[b+1][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;
}
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);
		v[i].first = x; v[i].second = y;
	}
	sort(v + 1, v + n + 1, comp);
	update(1, n, 0);
	for(; (1<<logn) <= n; logn++); logn--;
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		x1 = poz(x1, 0)+1; 
		x2 = poz(x2, 1);
		if(x1 > x2) x1--;
		query(1, n, 0);
		printf("%d\n", sol);
	}
	return 0;
}