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 //Marcin Knapik, Potyczki Algorytmiczne, Dzień 3, zadanie "Terytoria"[B] //złożoność O(n log n) #include using namespace std; #define ll long long #define pb push_back #define f first #define s second #define all(s) s.begin(), s.end() #define sz(s) (int)s.size() #define ull unsigned ll #define FOR(i, z) for(int i = 0; i < z; i++) #define losuj(a, b) uniform_int_distribution(a, b)(rng) ll n, X, Y; const unsigned ll MAX_LL = 0xFFFFFFFFFFFFFFFF; mt19937 rng(51); int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> X >> Y; vector> tab[2]; tab[0].pb({X, 0}); tab[1].pb({Y, 0}); for(int i = 0; i < n ; i++){ int a, b, c, d; cin >> a >> b >> c >> d; if(a > c) swap(a, c); if(b > d) swap(b, d); ull id = losuj(1, MAX_LL); tab[0].pb({a, id}); tab[0].pb({c, id}); tab[1].pb({b, id}); tab[1].pb({d, id}); } FOR(i, 2) sort(all(tab[i])); map mapa[2]; ll maxi[2] = {0, 0}; ll poz[2] = {0, 0}; FOR(i, 2){ ull hasz = 0; for(auto&u:tab[i]){ if(!mapa[i].count(hasz)) mapa[i][hasz] = u.f - poz[i]; else mapa[i][hasz] += u.f - poz[i]; poz[i] = u.f; maxi[i] = max(maxi[i], mapa[i][hasz]); hasz = hasz^u.s; } } cout << maxi[0] * maxi[1] << '\n'; }