1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
#include <list>
#include <vector>

//------------------------------------------------------------------------------

#define MAX_PRIME 7368787
#define MAX_QUOTIENT 2714

#define MODULO_PRIME 4294967029u

unsigned PRIMES[500000];

unsigned INVERSES[500000];

// source: https://rosettacode.org
unsigned mul_inv(unsigned a, unsigned b)
{
	long long b0 = b, t, q;
	long long x0 = 0, x1 = 1;
	if (b==1) return 1;
	while (a>1) {
		q = a/b;
		t = b, b = a%b, a = t;
		t = x0, x0 = x1-q*x0, x1 = t;
	}
	if (x1<0) x1 += b0;
	return x1;
}

unsigned mul(unsigned a, unsigned b)
{
	return (static_cast<unsigned long long>(a)*static_cast<unsigned long long>(b))%MODULO_PRIME;
}

void fill_primes()
{
	std::vector<unsigned char> sieve(1+MAX_PRIME, 1);
	sieve[0] = sieve[1] = 0;
	for (int q = 2; q<=MAX_QUOTIENT; ++q) {
		if (sieve[q]) {
			for (int n = 2*q; n<=MAX_PRIME; n += q) {
				sieve[n] = 0;
			}
		}
	}
	int index = 0;
	for (int p = 2; p<=MAX_PRIME; ++p) {
		if (sieve[p]) {
			unsigned q = mul_inv(p, MODULO_PRIME);
//			if (mul(p, q) != 1) exit(1);
			INVERSES[index] = q;
			PRIMES[index++] = p;
		}
	}
}

//------------------------------------------------------------------------------

using hash_t = unsigned long long;

void entering(hash_t& hash, int number)
{
	unsigned* view = reinterpret_cast<unsigned*>(&hash);
	view[0] = mul(view[0], PRIMES[number]);
	view[1] += number;
}

void exiting(hash_t& hash, int number)
{
	unsigned* view = reinterpret_cast<unsigned*>(&hash);
	view[0] = mul(view[0], INVERSES[number]);
	view[1] -= number;
}

//------------------------------------------------------------------------------

struct Endpoint {
	unsigned position;
	int number; // interval ID >= 0
	bool starting; // whether starting or ending endpoint

	bool operator<(const Endpoint& e) const
	{
		return (position<e.position) || (position==e.position && number<e.number);
	}
};

unsigned get_max_length(const std::vector<Endpoint>& endpoints, unsigned MAX)
{
	hash_t hash = 1;
	std::unordered_map<hash_t, unsigned> lengths;

	unsigned position = 0;
	unsigned max_length = 0;
	for (const Endpoint& endpoint : endpoints) {
		if (endpoint.position > position) {
			max_length = std::max(max_length, lengths[hash] += endpoint.position - position);
		}
		if (endpoint.starting) {
			entering(hash, endpoint.number);
		} else {
			exiting(hash, endpoint.number);
		}
		position = endpoint.position;
	}
	if (MAX > position) {
		max_length = std::max(max_length, lengths[hash] += MAX - position);
	}
	return max_length;
}

int main()
{
	int N;
	unsigned X, Y;
	if (scanf("%d%u%u", &N, &X, &Y)!=3) exit(1);

	fill_primes();

	std::vector <Endpoint> x_endpoints, y_endpoints;
	x_endpoints.reserve(2*N);
	y_endpoints.reserve(2*N);
	for (int i = 0; i<N; ++i) {
		unsigned x1, y1, x2, y2;
		if (scanf("%u%u%u%u", &x1, &y1, &x2, &y2)!=4) exit(1);
		if (x1>x2) std::swap(x1, x2);
		if (y1>y2) std::swap(y1, y2);
		x_endpoints.push_back({x1, i, true});
		x_endpoints.push_back({x2, i, false});
		y_endpoints.push_back({y1, i, true});
		y_endpoints.push_back({y2, i, false});
	}
	std::sort(x_endpoints.begin(), x_endpoints.end());
	std::sort(y_endpoints.begin(), y_endpoints.end());

	unsigned max_length_x = get_max_length(x_endpoints, X);
	unsigned max_length_y = get_max_length(y_endpoints, Y);

	printf("%llu\n", static_cast<unsigned long long>(max_length_x) * static_cast<unsigned long long>(max_length_y));
}