#include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> primes = {3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83}; int compute_len(int size, vector<int>& x1, vector<int>& x2, int w) { int i, j; vector<unsigned long long> hash1 = vector<unsigned long long>(size, 0LL); vector<unsigned long long> hash2 = vector<unsigned long long>(size, 0LL); vector<pair<int, int>> points; for (i = 0; i < x1.size(); ++i) { points.push_back(make_pair(x1[i], i)); points.push_back(make_pair(x2[i], i)); } sort(points.begin(), points.end()); i = 0; vector<pair<pair<unsigned long long, unsigned long long>, int>> lens; while (true) { j = i; while (j < points.size() && points[i].first == points[j].first) { int num = size / 2 + points[j].second - 1; hash1[num] = 1 - hash1[num]; hash2[num] = 1 - hash2[num]; int v = 1; while (num > 0) { num = (num - 1) / 2; hash1[num] = (hash1[(num + 1) * 2] + hash1[(num + 1) * 2 - 1] * primes[primes.size() - 1]) % 1000000007LL; hash2[num] = (((hash2[(num + 1) * 2] + hash2[(num + 1) * 2 - 1] * primes[v - 1]) % 1000000007LL) * v) % 1000000007LL; v++; } j++; } auto hash = make_pair(hash1[0], hash2[0]); if (j < points.size()) { lens.push_back(make_pair(hash, points[j].first - points[j - 1].first)); } else { lens.push_back(make_pair(hash, w - points[j - 1].first + points[0].first)); break; } i = j; } sort(lens.begin(), lens.end()); int ma = 0; i = 0; while (i < lens.size()) { int sum = 0; j = i; while (j < lens.size() && lens[i].first == lens[j].first) { sum += lens[j].second; j++; } ma = max(sum, ma); i = j; } return ma; } int main() { int n, x, y, i, j, size; scanf("%d%d%d", &n, &x, &y); vector<int> x1(n, 0), x2(n, 0), y1(n, 0), y2(n, 0); size = 1; while (size < n) { size *= 2; } size *= 2; for (i = 0; i < n; ++i) { scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]); } long long a = compute_len(size, x1, x2, x); long long b = compute_len(size, y1, y2, y); printf("%lld", a * b); 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 | #include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> primes = {3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83}; int compute_len(int size, vector<int>& x1, vector<int>& x2, int w) { int i, j; vector<unsigned long long> hash1 = vector<unsigned long long>(size, 0LL); vector<unsigned long long> hash2 = vector<unsigned long long>(size, 0LL); vector<pair<int, int>> points; for (i = 0; i < x1.size(); ++i) { points.push_back(make_pair(x1[i], i)); points.push_back(make_pair(x2[i], i)); } sort(points.begin(), points.end()); i = 0; vector<pair<pair<unsigned long long, unsigned long long>, int>> lens; while (true) { j = i; while (j < points.size() && points[i].first == points[j].first) { int num = size / 2 + points[j].second - 1; hash1[num] = 1 - hash1[num]; hash2[num] = 1 - hash2[num]; int v = 1; while (num > 0) { num = (num - 1) / 2; hash1[num] = (hash1[(num + 1) * 2] + hash1[(num + 1) * 2 - 1] * primes[primes.size() - 1]) % 1000000007LL; hash2[num] = (((hash2[(num + 1) * 2] + hash2[(num + 1) * 2 - 1] * primes[v - 1]) % 1000000007LL) * v) % 1000000007LL; v++; } j++; } auto hash = make_pair(hash1[0], hash2[0]); if (j < points.size()) { lens.push_back(make_pair(hash, points[j].first - points[j - 1].first)); } else { lens.push_back(make_pair(hash, w - points[j - 1].first + points[0].first)); break; } i = j; } sort(lens.begin(), lens.end()); int ma = 0; i = 0; while (i < lens.size()) { int sum = 0; j = i; while (j < lens.size() && lens[i].first == lens[j].first) { sum += lens[j].second; j++; } ma = max(sum, ma); i = j; } return ma; } int main() { int n, x, y, i, j, size; scanf("%d%d%d", &n, &x, &y); vector<int> x1(n, 0), x2(n, 0), y1(n, 0), y2(n, 0); size = 1; while (size < n) { size *= 2; } size *= 2; for (i = 0; i < n; ++i) { scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]); } long long a = compute_len(size, x1, x2, x); long long b = compute_len(size, y1, y2, y); printf("%lld", a * b); return 0; } |