Cod sursa(job #25517)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 4 martie 2007 12:48:46
Problema Ograzi Scor 60
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.47 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MP make_pair

const int NMAX = 1 << 17;

int N, M, W, H;
vector <pair <int, int> > P;
vector <int> AI[NMAX];
int UY, DY, cnt;

inline bool cifra(const char c) { return c >= '0' && c <= '9'; }

void readline(FILE *fin, int V[]) {
	int nv = 0, i, aux;
	char S[64];

	fgets(S, 64, fin);

	for (i = 0; !cifra(S[i]); ++i);

	while (S[i]) {
		
		for (aux = 0; cifra(S[i]); ++i)
			aux = aux * 10 + (S[i] - '0');

		for (; S[i] && !cifra(S[i]); ++i);

		V[nv++] = aux;
	}
}

void construct(int st, int dr, int i) {
//	printf("construct %d %d %d\n", st, dr, i);
	if (st == dr) {
		AI[i].resize(1);
		AI[i][0] = P[st].second;
//		printf("constructed %u => %d\n", AI[i].size(), AI[i][0]);
	} else {
		int mij, is, id, j, k, t, ds, dd;

		mij = (st + dr) >> 1;
		is = i << 1; id = is | 1;

		construct(st, mij, is);
		construct(mij + 1, dr, id);

		ds = AI[is].size();
		dd = AI[id].size();
		AI[i].resize(ds + dd);
//		printf("%d %d %u\n", ds, dd, AI[i].size());

		for (t = j = k = 0; j < ds || k < dd; ++t)
			if (j >= ds || (k < dd && AI[id][k] < AI[is][j]))
				AI[i][t] = AI[id][k++];
			else
				AI[i][t] = AI[is][j++];
	}
}

bool query(int st, int dr, int i, int a, int b) {
//	printf("%d(%d) %d(%d) %d %d %d\n", st, P[st].first, dr, P[dr].first, i, a, b);
	if (a <= P[st].first && P[dr].first <= b) {
		return upper_bound(AI[i].begin(), AI[i].end(), UY) - lower_bound(AI[i].begin(), AI[i].end(), DY);
	}

	int mij, is, id;
	
	mij = (st + dr) >> 1;
	is = i << 1; id = is | 1;

	if (a <= P[mij].first && query(st, mij, is, a, b))
		return true;
	
	if (b >= P[mij + 1].first && query(mij + 1, dr, id, a, b))
		return true;

	return false;
}

void write() {
	FILE *fout = fopen("ograzi.out", "wt");

	fprintf(fout, "%d\n", cnt);

	fclose(fout);
}

int main() {

	FILE *fin = fopen("ograzi.in", "rt");
	int V[8], i, UX, DX;

	readline(fin, V);
	N = V[0]; M = V[1]; W = V[2]; H = V[3];
//	printf("%d %d %d %d\n", N, M, W, H);

	P.resize(N);
//	printf("P = %u\n", P.size());

	for (i = 0; i < N; ++i) {
		readline(fin, V);
		P[i] = MP(V[0], V[1]);
//		printf("P[%d] = (%d,%d)\n", i, P[i].first, P[i].second);
	}

	sort(P.begin(), P.end());

	construct(0, N - 1, 1);

	for (i = 0; i < M; ++i) {
		readline(fin, V);
//		printf("read %d %d\n", V[0], V[1]);

		UY = V[1]; DY = UY - H;
		UX = min(P[N - 1].first, V[0]);
		DX = max(P[0].first, V[0] - W);

		if (DX <= UX && query(0, N - 1, 1, DX, UX))
			++cnt;
	}

	write();

	fclose(fin);

	return 0;
}