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 120 121 #include #include #include #include #include #include #include #include using namespace std; int N, L, X, Y; vector, int>> T; vector X2i, Y2i; vector> XX, YY; pair f(const pair, int> &L, const pair, int> &R) { return {(L.second ? L.first.second : L.first.first) + (R.second ? R.first.second : R.first.first), L.first.second + R.first.second}; } int fff(const pair, int> &L, const pair, int> &R) { return (L.second ? L.first.second : L.first.first) + (R.second ? R.first.second : R.first.first); } void add(int l, int r, int x, int y=0) { if (l==r) return; if (l>r) { add(r, l, y, x); // add(0, r, x); // add(l, L-1, x); return; } l+=L; r+=L; T[l].second+=x; T[r].second+=y; while (l/2!=r/2) { if (l%2==0) T[l+1].second+=x; else T[l-1].second+=y; if (r%2==1) T[r-1].second+=x; else T[r+1].second+=y; l/=2; r/=2; T[l].first.first=fff(T[2*l], T[2*l+1]); T[r].first.first=fff(T[2*r], T[2*r+1]); // T[l].first=f(T[2*l], T[2*l+1]); // T[r].first=f(T[2*r], T[2*r+1]); } while (l>1) { l/=2; T[l].first.first=fff(T[2*l], T[2*l+1]); // T[l].first=f(T[2*l], T[2*l+1]); T[l^1].second+=y; } } int main() { ios::sync_with_stdio(false); cin >> N >> X >> Y; X2i.push_back(0); X2i.push_back(X); Y2i.push_back(0); Y2i.push_back(Y); for (int i=0; i> x1 >> y1>> x2 >> y2; if (x1>x2) swap(x1, x2); if (y1>y2) swap(y1, y2); X2i.push_back(x1); X2i.push_back(x2); Y2i.push_back(y1); Y2i.push_back(y2); XX.emplace_back(x1, x2); XX.emplace_back(x2, x1); YY.emplace_back(y1, y2); YY.emplace_back(y2, y1); } long long res=1; for (int kkk=0; kkk<2; kkk++){ sort(X2i.begin(), X2i.end()); X2i.resize(unique(X2i.begin(), X2i.end())-X2i.begin()); sort(XX.begin(), XX.end()); L=1; while (L<=(int)X2i.size()) L*=2; T.clear(); T.resize(2*L); for (int i=0; i<(int)X2i.size()-1; i++){ T[L+i].first.second=X2i[i+1]-X2i[i]; } for(int i=L-1; i>0; i--) { T[i].first=f(T[2*i], T[2*i+1]); } for (auto p:XX) { if (p.first>p.second) continue; int idx1=lower_bound(X2i.begin(), X2i.end(), p.first)-X2i.begin(); int idx2=lower_bound(X2i.begin(), X2i.end(), p.second)-X2i.begin(); add(idx1, idx2, 1); } int lRes=X-T[1].first.first; // cout << "!!! " << lRes << endl; for (auto p:XX) { int idx1=lower_bound(X2i.begin(), X2i.end(), p.first)-X2i.begin(); int idx2=lower_bound(X2i.begin(), X2i.end(), p.second)-X2i.begin(); add(idx1, idx2, -1, 1); // add(idx1, idx2, -1); // add(idx2, idx1, 1); lRes=max(lRes,X-T[1].first.first); // cout << "!!! " << lRes << endl; } res*=lRes; X2i=Y2i; XX=YY; X=Y; } cout << res << endl; }