#include<cstdio> #include<algorithm> #include<vector> #define S 500007 #define M 2097152 using namespace std; typedef long long ll; int tree[2*M+7]; int tree2[2*M+7]; int lazy[2*M+7]; vector < pair < int ,int > > poczX; vector < int > justX; vector < pair < int, int > > poczY; vector < pair < pair < int , int > , int > > oper; pair < int , int > Prz[2*M+7]; void Add(int l, int r, int w, int c){ if(l > Prz[w].second || r < Prz[w].first) return; if(l <= Prz[w].first && r >= Prz[w].second){ //printf("%d %d %d %d %d %d*\n",w,c,l,r,Prz[w].first,Prz[w].second); tree[w]+=c; lazy[w]+=c; return; } lazy[w*2] += lazy[w]; lazy[w*2+1] += lazy[w]; tree[w*2] += lazy[w]; tree[w*2+1] += lazy[w]; lazy[w] = 0; Add(l,r,w*2,c); Add(l,r,w*2+1,c); if(tree[w*2] == tree[w*2+1]){ tree[w] = tree[w*2]; tree2[w] = tree2[w*2] + tree2[w*2+1]; }else{ tree[w] = max(tree[w*2],tree[w*2+1]); if(tree[w*2] > tree[w*2+1]){ tree2[w] = tree2[w*2]; }else{ tree2[w] = tree2[w*2+1]; } } } int x,y; void dodaj(int l, int r, int c){ //printf("%d %d %d##\n",l,r,c); if(r >= l){ Add(l,r,1,c); }else{ } } int main(void){ int n; int a,b,c,d; scanf("%d %d %d",&n,&x,&y); for(int i = 1; i <= n;i++){ scanf("%d %d %d %d",&a,&b,&c,&d); if(a > c) swap(a,c); if(b > d) swap(b,d); a++; b++; poczX.push_back({a,c}); poczY.push_back({b,d}); oper.push_back({{a,c},1}); oper.push_back({{c,a},0}); justX.push_back(a); justX.push_back(c); } sort(poczX.begin(),poczX.end()); sort(justX.begin(),justX.end()); sort(oper.begin(),oper.end()); int p = M; Prz[p].first = 1; Prz[p].second = justX[0]-1; if(Prz[p].second == 0) Prz[p].second++; else{ p++; Prz[p] = {justX[0],justX[0]}; } for(int i = 1; i < justX.size();i++){ if(justX[i] == 1) continue; if(justX[i] == justX[i-1]){ continue; }else if(justX[i] == justX[i-1] + 1){ p++; Prz[p] = {justX[i],justX[i]}; }else{ p++; Prz[p] = {justX[i-1]+1,justX[i]-1}; p++; Prz[p] = {justX[i],justX[i]}; } } if(Prz[p].second != x){ p++; Prz[p] = {Prz[p-1].second+1,x}; } for(int i = M; i <= p;i++){ tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = M-1; i>= 1;i--){ if(Prz[i*2+1].second){ Prz[i].second = Prz[i*2+1].second; }else{ Prz[i].second = Prz[i*2].second; } Prz[i].first = Prz[i*2].first; tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = 0 ; i < poczX.size();i++){ dodaj(1,poczX[i].first-1,1); dodaj(poczX[i].second+1,x,1); } int odp = 0; if(tree[1] == n){ odp = tree2[1]; } //printf("%d %d*\n",tree[1],tree2[1]); for(int i = 0; i < oper.size();i++){ a = oper[i].first.first; b = oper[i].first.second; if(a < b){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else if (a > b){ dodaj(b,a,-1); dodaj(a+1,x,1); dodaj(1,b-1,1); }else{ if(oper[i].second == 0){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else{ dodaj(a,b,-1); dodaj(1,a-1,1); dodaj(b+1,x,1); } } //printf("%d %d*\n",tree[1],tree2[1]); if(tree[1] == n){ //printf("AASD"); odp = max(odp,tree2[1]); } } for(int i = 1; i < 2*M;i++){ tree[i] = tree2[i] = lazy[i] = 0; Prz[i] = {0,0}; } justX.clear(); oper.clear(); poczX.clear(); x = y; for(int i = 0; i < n;i++){ a = poczY[i].first; c = poczY[i].second; poczX.push_back({a,c}); oper.push_back({{a,c},1}); oper.push_back({{c,a},0}); justX.push_back(a); justX.push_back(c); } sort(poczX.begin(),poczX.end()); sort(justX.begin(),justX.end()); sort(oper.begin(),oper.end()); p = M; Prz[p].first = 1; Prz[p].second = justX[0]-1; if(Prz[p].second == 0) Prz[p].second++; else{ p++; Prz[p] = {justX[0],justX[0]}; } for(int i = 1; i < justX.size();i++){ if(justX[i] == 1) continue; if(justX[i] == justX[i-1]){ continue; }else if(justX[i] == justX[i-1] + 1){ p++; Prz[p] = {justX[i],justX[i]}; }else{ p++; Prz[p] = {justX[i-1]+1,justX[i]-1}; p++; Prz[p] = {justX[i],justX[i]}; } } if(Prz[p].second != x){ p++; Prz[p] = {Prz[p-1].second+1,x}; } for(int i = M; i <= p;i++){ tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = M-1; i>= 1;i--){ if(Prz[i*2+1].second){ Prz[i].second = Prz[i*2+1].second; }else{ Prz[i].second = Prz[i*2].second; } Prz[i].first = Prz[i*2].first; tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = 0 ; i < poczX.size();i++){ dodaj(1,poczX[i].first-1,1); dodaj(poczX[i].second+1,x,1); } int odp2 = 0; if(tree[1] == n){ odp2 = tree2[1]; } //printf("%d %d*\n",tree[1],tree2[1]); for(int i = 0; i < oper.size();i++){ a = oper[i].first.first; b = oper[i].first.second; if(a < b){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else if (a > b){ dodaj(b,a,-1); dodaj(a+1,x,1); dodaj(1,b-1,1); }else{ if(oper[i].second == 0){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else{ dodaj(a,b,-1); dodaj(1,a-1,1); dodaj(b+1,x,1); } } //printf("%d %d*\n",tree[1],tree2[1]); if(tree[1] == n){ //printf("AASD"); odp2 = max(odp2,tree2[1]); } } ll odp3 = (ll)odp; odp3 *= (ll)odp2; printf("%lld",odp3); return 0; }
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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 | #include<cstdio> #include<algorithm> #include<vector> #define S 500007 #define M 2097152 using namespace std; typedef long long ll; int tree[2*M+7]; int tree2[2*M+7]; int lazy[2*M+7]; vector < pair < int ,int > > poczX; vector < int > justX; vector < pair < int, int > > poczY; vector < pair < pair < int , int > , int > > oper; pair < int , int > Prz[2*M+7]; void Add(int l, int r, int w, int c){ if(l > Prz[w].second || r < Prz[w].first) return; if(l <= Prz[w].first && r >= Prz[w].second){ //printf("%d %d %d %d %d %d*\n",w,c,l,r,Prz[w].first,Prz[w].second); tree[w]+=c; lazy[w]+=c; return; } lazy[w*2] += lazy[w]; lazy[w*2+1] += lazy[w]; tree[w*2] += lazy[w]; tree[w*2+1] += lazy[w]; lazy[w] = 0; Add(l,r,w*2,c); Add(l,r,w*2+1,c); if(tree[w*2] == tree[w*2+1]){ tree[w] = tree[w*2]; tree2[w] = tree2[w*2] + tree2[w*2+1]; }else{ tree[w] = max(tree[w*2],tree[w*2+1]); if(tree[w*2] > tree[w*2+1]){ tree2[w] = tree2[w*2]; }else{ tree2[w] = tree2[w*2+1]; } } } int x,y; void dodaj(int l, int r, int c){ //printf("%d %d %d##\n",l,r,c); if(r >= l){ Add(l,r,1,c); }else{ } } int main(void){ int n; int a,b,c,d; scanf("%d %d %d",&n,&x,&y); for(int i = 1; i <= n;i++){ scanf("%d %d %d %d",&a,&b,&c,&d); if(a > c) swap(a,c); if(b > d) swap(b,d); a++; b++; poczX.push_back({a,c}); poczY.push_back({b,d}); oper.push_back({{a,c},1}); oper.push_back({{c,a},0}); justX.push_back(a); justX.push_back(c); } sort(poczX.begin(),poczX.end()); sort(justX.begin(),justX.end()); sort(oper.begin(),oper.end()); int p = M; Prz[p].first = 1; Prz[p].second = justX[0]-1; if(Prz[p].second == 0) Prz[p].second++; else{ p++; Prz[p] = {justX[0],justX[0]}; } for(int i = 1; i < justX.size();i++){ if(justX[i] == 1) continue; if(justX[i] == justX[i-1]){ continue; }else if(justX[i] == justX[i-1] + 1){ p++; Prz[p] = {justX[i],justX[i]}; }else{ p++; Prz[p] = {justX[i-1]+1,justX[i]-1}; p++; Prz[p] = {justX[i],justX[i]}; } } if(Prz[p].second != x){ p++; Prz[p] = {Prz[p-1].second+1,x}; } for(int i = M; i <= p;i++){ tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = M-1; i>= 1;i--){ if(Prz[i*2+1].second){ Prz[i].second = Prz[i*2+1].second; }else{ Prz[i].second = Prz[i*2].second; } Prz[i].first = Prz[i*2].first; tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = 0 ; i < poczX.size();i++){ dodaj(1,poczX[i].first-1,1); dodaj(poczX[i].second+1,x,1); } int odp = 0; if(tree[1] == n){ odp = tree2[1]; } //printf("%d %d*\n",tree[1],tree2[1]); for(int i = 0; i < oper.size();i++){ a = oper[i].first.first; b = oper[i].first.second; if(a < b){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else if (a > b){ dodaj(b,a,-1); dodaj(a+1,x,1); dodaj(1,b-1,1); }else{ if(oper[i].second == 0){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else{ dodaj(a,b,-1); dodaj(1,a-1,1); dodaj(b+1,x,1); } } //printf("%d %d*\n",tree[1],tree2[1]); if(tree[1] == n){ //printf("AASD"); odp = max(odp,tree2[1]); } } for(int i = 1; i < 2*M;i++){ tree[i] = tree2[i] = lazy[i] = 0; Prz[i] = {0,0}; } justX.clear(); oper.clear(); poczX.clear(); x = y; for(int i = 0; i < n;i++){ a = poczY[i].first; c = poczY[i].second; poczX.push_back({a,c}); oper.push_back({{a,c},1}); oper.push_back({{c,a},0}); justX.push_back(a); justX.push_back(c); } sort(poczX.begin(),poczX.end()); sort(justX.begin(),justX.end()); sort(oper.begin(),oper.end()); p = M; Prz[p].first = 1; Prz[p].second = justX[0]-1; if(Prz[p].second == 0) Prz[p].second++; else{ p++; Prz[p] = {justX[0],justX[0]}; } for(int i = 1; i < justX.size();i++){ if(justX[i] == 1) continue; if(justX[i] == justX[i-1]){ continue; }else if(justX[i] == justX[i-1] + 1){ p++; Prz[p] = {justX[i],justX[i]}; }else{ p++; Prz[p] = {justX[i-1]+1,justX[i]-1}; p++; Prz[p] = {justX[i],justX[i]}; } } if(Prz[p].second != x){ p++; Prz[p] = {Prz[p-1].second+1,x}; } for(int i = M; i <= p;i++){ tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = M-1; i>= 1;i--){ if(Prz[i*2+1].second){ Prz[i].second = Prz[i*2+1].second; }else{ Prz[i].second = Prz[i*2].second; } Prz[i].first = Prz[i*2].first; tree2[i] = Prz[i].second - Prz[i].first+1; } for(int i = 0 ; i < poczX.size();i++){ dodaj(1,poczX[i].first-1,1); dodaj(poczX[i].second+1,x,1); } int odp2 = 0; if(tree[1] == n){ odp2 = tree2[1]; } //printf("%d %d*\n",tree[1],tree2[1]); for(int i = 0; i < oper.size();i++){ a = oper[i].first.first; b = oper[i].first.second; if(a < b){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else if (a > b){ dodaj(b,a,-1); dodaj(a+1,x,1); dodaj(1,b-1,1); }else{ if(oper[i].second == 0){ dodaj(a,b,1); dodaj(1,a-1,-1); dodaj(b+1,x,-1); }else{ dodaj(a,b,-1); dodaj(1,a-1,1); dodaj(b+1,x,1); } } //printf("%d %d*\n",tree[1],tree2[1]); if(tree[1] == n){ //printf("AASD"); odp2 = max(odp2,tree2[1]); } } ll odp3 = (ll)odp; odp3 *= (ll)odp2; printf("%lld",odp3); return 0; } |