Cod sursa(job #3292642)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 8 aprilie 2025 20:29:41
Problema Ograzi Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <stdio.h>
#include <ctype.h>
using namespace std;
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
struct elem{
	int x, y;
};
struct fast_elem{
	int poz1, poz2, x;
};
struct fast_map{
	const int MOD = 983875;
	vector <fast_elem> v[983875];
	
	void add_elem(int poz1, int poz2, int x){
		int a;
		poz1++;
		poz2++;
		a = ( 1ll * ( poz1 + poz2 ) * ( poz1 + poz2 + 1 ) / 2 + poz2 ) % MOD;
		v[a].push_back( { poz1, poz2, x } );
	}

	int get_elem(int poz1, int poz2){
		int x, i;
		//return -1;
		poz1++;
		poz2++;
		x = ( 1ll * ( poz1 + poz2 ) * ( poz1 + poz2 + 1 ) / 2 + poz2 ) % MOD;
		//cout << poz1 << ' ' << poz2 << ' ' << x << '\n';
		i = 0;
		while( i < v[x].size() && ( v[x][i].poz1 != poz1 || v[x][i].poz2 != poz2 ) ){
			i++;
		}
		//cout << i << '\n';
		if( i < v[x].size() ){
			return v[x][i].x;
		}
		return -1;
	}
};
vector <elem> v;
fast_map f;
int w, h;
static inline int check(int x, int y, int poz){
	if( poz == -1 ){
		return 0;
	}
	//cout << x << ' ' << y << ' ' << v[poz].x << ' ' << v[poz].y << '\n';
	if( v[poz].x <= x && v[poz].y <= y && v[poz].x + w >= x && v[poz].y + h >= y ){
		return 1;
	}
	return 0;
}
int main(){
	int n, m, i, x, y, r, ad;
	//elem a;
	InParser fin( "ograzi.in" );
	ofstream fout( "ograzi.out" );
	fin >> n >> m >> w >> h;
	//fin.get();
	for( i = 0; i < n; i++ ){
		//a = read();
		fin >> x >> y;
		/*x = a.x;
		y = a.y;*/
		//cout << x << ' ' << y << '\n';
		v.push_back( { x, y } );
		f.add_elem( x / w, y / h, i );
	}
	r = 0;
	for( i = 0; i < m; i++ ){
		//a = read();
		fin >> x >> y;
		/*x = a.x;
		y = a.y;*/
		//cout << x << ' ' << y << '\n';
		ad = max( check( x, y, f.get_elem( x / w, y / h ) ), check( x, y, f.get_elem( x / w - 1, y / h ) ) );
		ad = max( check( x, y, f.get_elem( x / w, y / h - 1 ) ), ad );
		ad = max( check( x, y, f.get_elem( x / w - 1, y / h - 1 ) ), ad );
		r += ad;
	}
	fout << r;
	return 0;
}