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
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <cstdlib>

#include <algorithm>
#include <unordered_map>
#include <vector>

struct seg_event_t {
  uint32_t position;
  int idx;
};

// Around 60 bits
const uint64_t MODULUS_PRIME = 999999999999999989;
// const uint64_t MODULUS_PRIME = 99999999999999997;

std::vector<uint64_t> compute_hash_table(int max_n,
                                         uint64_t advancement,
                                         uint64_t modulus) {
  std::vector<uint64_t> ret;
  ret.reserve(max_n + 1);

  uint64_t current = 1;
  ret.push_back(1);
  for (int i = 1; i <= max_n; i++) {
    current = (current * advancement) % modulus;
    ret.push_back(current);
    assert(current != 1 && current != 0);
  }

  return ret;
}

uint64_t process_coord(std::vector<seg_event_t> evts,
                       const std::vector<uint64_t>& htable,
                       uint32_t limit) {
  auto comparator = [](const seg_event_t& a, const seg_event_t& b) -> bool {
    return a.position < b.position;
  };
  std::sort(evts.begin(), evts.end(), comparator);

  std::unordered_map<uint64_t, uint64_t> area_for_set;
  uint64_t set_marker = 0;

  uint32_t previous_position = 0;
  for (const auto e : evts) {
    const auto length = e.position - previous_position;
    area_for_set[set_marker] += length;
    previous_position = e.position;
    if (e.idx > 0) {
      set_marker += htable[e.idx];
    } else {
      set_marker += MODULUS_PRIME - htable[-e.idx];
    }
    set_marker %= MODULUS_PRIME;
  }

  area_for_set[set_marker] += limit - previous_position;

  uint64_t max = 0;
  for (auto p : area_for_set) {
    max = std::max(max, p.second);
  }

  return max;
}

int main() {
  unsigned int n, X, Y;
  (void)scanf("%u %u %u", &n, &X, &Y);

  std::vector<seg_event_t> hor_evts, ver_evts;
  hor_evts.reserve(2 * n);
  ver_evts.reserve(2 * n);

  for (int i = 1; i <= (int)n; i++) {
    unsigned int x1, y1, x2, y2;
    (void)scanf("%u %u %u %u", &x1, &y1, &x2, &y2);
    hor_evts.push_back(seg_event_t{x1, i});
    hor_evts.push_back(seg_event_t{x2, -i});
    ver_evts.push_back(seg_event_t{y1, i});
    ver_evts.push_back(seg_event_t{y2, -i});
  }

  const auto htable = compute_hash_table(n, 7, MODULUS_PRIME);
  const auto solution = process_coord(std::move(hor_evts), htable, X) *
                        process_coord(std::move(ver_evts), htable, Y);

  printf("%llu\n", (unsigned long long int)solution);

  return 0;
}