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
#include <bits/stdc++.h>
using namespace std;
constexpr long long pot[2] = {229, 313};
constexpr long long mod[2] = {29996224275833, 252097800623};
vector <long long> potegi[2];
int n, X, Y;
// Dla posortowanego wektora zmian oblicza najszerszy bok tego samego zbioru
int licz_bok(const vector <pair <int, int> > &war) {
   map <pair <long long, long long>, int > mapcia;
   vector <int> stany(n+1, 0);
   long long h1 = 0; long long h2 = 0;
   int ost = 0;
   for (int i = 0; i < war.size(); i++) {
       int x = war[i].first;
       mapcia[{h1, h2}]+= (x - ost); // +-1?
       ost = x;
       while (i < war.size() && war[i].first == x) {
            int id = war[i].second;
            h1 = ((h1 - potegi[0][id]*stany[id] + mod[0]) % mod[0]); // zabieram poprzedni stan
            h2 = ((h2 - potegi[1][id]*stany[id] + mod[1]) % mod[1]);
            stany[id] = (stany[id] + 1)%2;
            h1 = ((h1 + potegi[0][id]*stany[id]) % mod[0]); // uaktualniam poprzedni stan
            h2 = ((h2 + potegi[1][id]*stany[id]) % mod[1]);
            i++;
       }
       i--;
   }
   int naj = 0;
   for (auto &c : mapcia) {
        naj = max(naj, c.second);
   }
   return naj;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector < pair <int, int> > kolumny;
    vector < pair <int, int> > rzedy;
    cin >> n >> X >> Y;
    // zmiany w kolumnach/wierszach
    for (int i = 0; i < 2; i++) {
        potegi[i].push_back(1);
        for (int j = 1; j <= 2*n; j++) {
            potegi[i].push_back((potegi[i].back()*pot[i])%mod[i]);
        }
    }

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        kolumny.push_back({X, i});
        kolumny.push_back({x1, i});
        kolumny.push_back({x2, i});
        rzedy.push_back({Y, i});
        rzedy.push_back({y1, i});
        rzedy.push_back({y2, i});
    }
    sort(kolumny.begin(), kolumny.end());
    sort(rzedy.begin(), rzedy.end());
    long long szer = licz_bok(rzedy);
    long long wys = licz_bok(kolumny);
    cout << szer*wys << "\n";
}