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
#include <bits/stdc++.h>

using namespace std;

using ll = long long int;
using pll = pair<long long int, long long int>;

const int MAXN = 500010;

ll p[MAXN][2];
ll k[MAXN][2];
ll dim[2];

ll pot[MAXN][2];
ll mod[2];


void hasz_add(pll &hasz, ll el) {
    hasz.first += pot[el - 1][0];
    if (hasz.first >= mod[0]) hasz.first -= mod[0];
    hasz.second += pot[el - 1][1];
    if (hasz.second >= mod[1]) hasz.second -= mod[1];
}

void hasz_rem(pll &hasz, ll el) {
    hasz.first -= pot[el - 1][0];
    if (hasz.first < 0) hasz.first += mod[0];
    hasz.second -= pot[el - 1][1];
    if (hasz.second < 0) hasz.second += mod[1];
}

int main() {
    int n;
    ll X[2];
    scanf("%d%lld%lld", &n, &X[0], &X[1]);

    mod[0] = 1008179971;
    mod[1] = 1034799671;
    pot[0][0] = 67;
    pot[0][1] = 67;
    for (int i = 1; i <= n; i++) {
        for (int d = 0; d < 2; d++) {
            pot[i][d] = (67 * pot[i - 1][d]) % mod[d];
        }
    }


    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld%lld", &p[i][0], &p[i][1], &k[i][0], &k[i][1]);
    }

    for (int d = 0; d < 2; d++) {
        vector<pair<ll, int>> ev;
        ev.push_back(make_pair(0, 0));
        ev.push_back(make_pair(X[d], 0));
        for (int i = 1; i <= n; i++) {
            ev.push_back(make_pair(min(p[i][d], k[i][d]), i));
            ev.push_back(make_pair(max(p[i][d], k[i][d]), -i));
        }
        sort(ev.begin(), ev.end());

        map<pll, ll> rozmy;
        pll hasz = make_pair(0, 0);
        ll pos = 0;
        for (int i = 0; i < ev.size(); i++) {
            if (ev[i].first != pos) {
                rozmy[hasz] += ev[i].first - pos;
                pos = ev[i].first;
            }
            if (ev[i].second > 0) {
                hasz_add(hasz, ev[i].second);
            }
            else if (ev[i].second < 0) {
                hasz_rem(hasz, -ev[i].second);
            }
        }

        for (auto it = rozmy.begin(); it != rozmy.end(); it++) {
            dim[d] = max(dim[d], it->second);
        }
    }

    printf("%lld\n", dim[0] * dim[1]);
}