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
//Autor: Mateusz Wasylkiewicz
//Zawody: Potyczki Algorytmiczne 2019
//Strona: http://potyczki.mimuw.edu.pl/
//Zadanie: Terytoria, runda 3B
//Czas: O(n*log(n)) (oczekiwany)
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef vector<LL> VI;
typedef pair<LL, LL> PII;
#define FOR(x, a, b) for (LL x = (a); x <= (b); x++)
#define FORD(x, a, b) for (LL x = (a); x >= (b); x--)
#define REP(x, n) for (LL x = 0; x < (n); x++)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) (LL((x).size()))
#define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); i++)
#define PB push_back
#define ST first
#define ND second
#define POKAZ(x) cerr << #x << " = " << (x) << '\n'

struct Zd
{
	LL x, nr;
	bool pocz;
	
	void ustaw(LL xx, LL numer, bool poczatek)
	{
		x = xx;
		nr = numer;
		pocz = poczatek;
	}
	
	bool operator < (const Zd& dane) const
	{
		if (x != dane.x)
			return x < dane.x;
		return nr < dane.nr;
	}
};

const LL MAX = 500100, P = 17, M = 167413876951462151LL;
LL n, rozmiar[2], pot[MAX + 1];
Zd zd[2][2 * (MAX + 1)];
unordered_map<LL, LL> licz;

void wczytaj_dane()
{
	cin >> n;
	REP(i, 2)
		cin >> rozmiar[i];
	REP(q, 2)
	{
		zd[q][0].ustaw(0, 0, true);
		zd[q][1].ustaw(rozmiar[q], 0, false);
	}
	FOR(nr, 1, n)
	{
		LL x[2][2];
		REP(i, 2)
			REP(j, 2)
				cin >> x[j][i];
		REP(q, 2)
		{
			if (x[q][0] > x[q][1])
				swap(x[q][0], x[q][1]);
			zd[q][2 * nr].ustaw(x[q][0], nr, true);
			zd[q][2 * nr + 1].ustaw(x[q][1], nr, false);
		}
	}
	n++;
}

void wypelnij_pot()
{
	pot[0] = 1;
	FOR(i, 1, MAX)
		pot[i] = (pot[i - 1] * P) % M;
}

inline void dodaj(LL& a, LL b)
{
	a += b;
	if (a >= M)
		a -= M;
}

inline void odejmij(LL& a, LL b)
{
	a -= b;
	if (a < 0)
		a += M;
}

LL rozwiaz(LL q)
{
	licz.clear();
	sort(zd[q], zd[q] + 2 * n);
	LL maks = 0, h = 0;
	REP(i, 2 * n - 1)
	{
		LL dl = zd[q][i + 1].x - zd[q][i].x;
		if (zd[q][i].pocz)
			dodaj(h, pot[zd[q][i].nr]);
		else
			odejmij(h, pot[zd[q][i].nr]);
		maks = max(maks, licz[h] += dl);
	}
	return maks;
}

void zrob_test()
{
	wczytaj_dane();
	wypelnij_pot();
	cout << (rozwiaz(0) * rozwiaz(1)) << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	zrob_test();
	return 0;
}