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
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
typedef unsigned long long int ULL;
typedef long long int LL;

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

const int N = 5e5 + 10;
const ULL P1 = 48271;
const ULL P2 = 6364136223846793005;

ULL ptsa1[2 * N], ptsa2[2 * N];

void pts(int n) {
    ptsa1[0] = 1;
    ptsa2[0] = 1;
    for (int i = 1; i <= 2 * n + 4; ++i) {
        ptsa1[i] = P1 * ptsa1[i - 1];
        ptsa2[i] = P2 * ptsa2[i - 1];
    }
}

struct S {
    bool start;
    int index;
    ULL x;
};

bool cmp(S& a, S& b) {
    if (a.x == b.x) {
        if (a.start == b.start) {
            return a.index < b.index;
        }
        return a.start < b.start;
    }
    return a.x < b.x;
}

ULL hsh1(ULL h, S& s) {
    if (s.start) {
        return h + ptsa1[s.index];
    }
    return h - ptsa1[s.index];
}

ULL hsh2(ULL h, S& s) {
    if (s.start) {
        return h + ptsa2[s.index];
    }
    return h - ptsa2[s.index];
}

ULL getMax(vector<S>& v, ULL X) {
    sort(v.begin(), v.end(), cmp);
    ULL h1 = 0, h2 = 0;
    int i = 0;
    ULL prevc = 0;
    ULL maxi = 0;
    unordered_map<pair<ULL, ULL>, ULL, pair_hash> mp;

    while (i < v.size()) {
        auto h = make_pair(h1, h2);
        if (mp.count(h)) {
            ULL l = mp[h] + v[i].x - prevc;
            maxi = max(maxi, l);
            mp[h] = l;
        } else {
            maxi = max(maxi, v[i].x - prevc);
            mp[h] = v[i].x - prevc;
        }
        prevc = v[i].x;

        h1 = hsh1(h1, v[i]);
        h2 = hsh2(h2, v[i]);
        while (i < v.size() - 1 && v[i + 1].x == v[i].x) {
            h1 = hsh1(h1, v[++i]);
            h2 = hsh2(h2, v[i]);
        }
        i++;
    }
    auto h = make_pair(h1, h2);
    if (mp.count(h)) {
        maxi = max(maxi, mp[h] + X - prevc);
    } else {
        maxi = max(maxi, X - prevc);
    }

    return maxi;
}

int main() {
    ios_base::sync_with_stdio(false);
    ULL n, X, Y, x1, x2, y1, y2;
    cin >> n >> X >> Y;
    pts(n);

    vector<S> vx, vy;

    for (int i = 0; i < n; ++i) {
        cin >> x1 >> y1 >> x2 >> y2;
        vx.push_back(S{true, i + 1, min(x1, x2)});
        vx.push_back(S{false, i + 1, max(x1, x2)});
        vy.push_back(S{true, i + 1, min(y1, y2)});
        vy.push_back(S{false, i + 1, max(y1, y2)});
    }

    cout << getMax(vx, X) * getMax(vy, Y) << endl;
}