Cod sursa(job #426256)

Utilizator andrei.12Andrei Parvu andrei.12 Data 26 martie 2010 17:41:56
Problema Ograzi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 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[lg1], p, punct[lg2], bag[lg1], ind;
vector<int> w[lg2];
pair<int, int> v[lg1];
char sir[30];

void add(int poz, int val){
	for (; poz <= m; 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 find(int val){
	int li = 1, ls = ind, x, gs = 0;

	while (li <= ls){
		x = (li + ls) / 2;

		if (bag[x] < val){
			gs = x;
			li = x + 1;
		}
		else
			ls = x - 1;
	}

	return gs;
}

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;

		punct[ v[i].y ] = 1;
	}

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

	for (i = 1; i <= 1000001; i ++){
		if (punct[i] == 1)
			bag[++ ind] = i;

		punct[i] += punct[i - 1];
	}

	sort(bag + 1, bag + ind + 1);
	//for (i = 1; i <= ind; i ++)
	//	printf("%d\n", bag[i]);

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

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

		
		for (j = 0; j < (int)w[i].size(); j ++){
			x = find(w[i][j] + H + 1); y = find(w[i][j]);
			//printf("%d %d  %d\n", x, y, query(x) - query(y));

			if (x > y)
				rsp += query(x) - query(y);
		}
	}

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

	return 0;
}