Cod sursa(job #426247)

Utilizator andrei.12Andrei Parvu andrei.12 Data 26 martie 2010 17:27:47
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define x first
#define y second

const int lg1 = 100005, lg2 = 1000005;

int n, m, W, H, x, y, i, end, st, j, rsp, d[lg2], p;
vector<int> w[lg2];
pair<int, int> v[lg1];
char sir[30];

void add(int poz, int val){
	for (; poz <= 1000001; poz += (poz ^ (poz - 1)) & poz)
		d[poz] += val;
}
int query(int poz){
	int rez = 0;

	for (; poz; poz -= (poz ^ (poz - 1)) & poz)
		rez += d[poz];

	return rez;
}

int nxt(){
	int x = 0, j;

	for (j = p; sir[j] >= '0' && sir[j] <= '9'; j ++)
		x = x * 10 + sir[j] - '0';
	p = j + 1;

	return x;
}

int main()
{
	freopen("ograzi.in", "rt", stdin);
	freopen("ograzi.out", "wt", stdout);

	scanf("%d%d%d%d\n", &n, &m, &W, &H);
	for (i = 1; i <= n; i ++){
		//scanf("%d%d", &x, &y);
		fgets(sir, 30, stdin); p = 0;
		x = nxt(), y = nxt();

		w[x + W + 1].push_back(y + 1);
	}
	for (i = 1; i <= m; i ++){
		//scanf("%d%d", &v[i].x, &v[i].y);
		fgets(sir, 30, stdin); p = 0;
		v[i].x = nxt() + 1, v[i].y = nxt() + 1;
	}

	sort(v + 1, v + m + 1);

	for (i = st = end = 1; i <= 1000001; i ++){
		for (; v[end].x == i && end <= m; end ++)
			add(v[end].y, 1);

		for (; v[st].x <= i - W - 1 && st <= m; st ++)
			add(v[st].y, -1);

		
		for (j = 0; j < (int)w[i].size(); j ++)
			rsp += query(w[i][j] + H) - query(w[i][j] - 1);
	}

	printf("%d\n", rsp);

	return 0;
}