// Author: Kamil Nizinski // NOLINT(legal/copyright) #ifdef LOCAL #ifdef COLOR #include "bits/cp_local_color.h" #else #include "bits/cp_local.h" #endif #else #include "bits/stdc++.h" #define debug_arr(arr_name, first, last) #define debug(...) #define cerr if (false) cerr #define speed_of_cin_and_cout ios_base::sync_with_stdio(0), cin.tie(0) #define local if (false) #endif #define ft first #define sd second #define psb push_back #define sz(a) (static_cast<int>((a).size())) using namespace std; // NOLINT(build/namespaces) typedef int64_t LL; typedef uint64_t LLU; typedef long double LD; typedef pair<int, int> PII; const int kMaxN = 500007; int largest_intersection_size(int start_dist, int end_dist, int p, int q, array<int, 2> *sorted_events, int *neighbours) { debug(p, q, sorted_events[p], sorted_events[q - 1]); debug(start_dist, end_dist); if (p == q) { debug(start_dist, end_dist); return end_dist - start_dist; } int r = neighbours[p]; debug(r, sorted_events[r]); if (p <= r && r < q) { cerr << "Double\n"; return max(largest_intersection_size(sorted_events[p][0], sorted_events[r][0], p + 1, r, sorted_events, neighbours), largest_intersection_size(sorted_events[r][0], end_dist + sorted_events[p][0] - start_dist, r, q, sorted_events, neighbours)); } else { cerr << "Single\n"; return max(sorted_events[p][0] - start_dist, largest_intersection_size(sorted_events[p][0], end_dist, p + 1, q, sorted_events, neighbours)); } } void solve() { int n; cin >> n; array<int, 2> lengths; for (int dir = 0; dir < 2; dir++) cin >> lengths[dir]; static array<int, 2> positions_of_pairs[2][kMaxN]; static array<int, 2> sorted_events[2][kMaxN << 1]; static int neighbours[2][kMaxN << 1]; for (int i = 0; i < n; i++) { int points[2][2]; for (int coor = 0; coor < 2; coor++) for (int dir = 0; dir < 2; dir++) cin >> points[dir][coor]; for (int dir = 0; dir < 2; dir++) { for (int coor = 0; coor < 2; coor++) sorted_events[dir][(i << 1) + coor] = {points[dir][coor], i}; positions_of_pairs[dir][i] = {-1, -1}; } } for (int dir = 0; dir < 2; dir++) { debug(dir); sort(sorted_events[dir], sorted_events[dir] + (n << 1)); debug_arr(sorted_events[dir], 0, (n << 1)); for (int i = 0; i < (n << 1); i++) { int idx = sorted_events[dir][i][1]; if (positions_of_pairs[dir][idx][0] == -1) positions_of_pairs[dir][idx][0] = i; else { positions_of_pairs[dir][idx][1] = i; for (int coor = 0; coor < 2; coor++) neighbours[dir][positions_of_pairs[dir][idx][coor]] = positions_of_pairs[dir][idx][1 - coor]; } } } array<int, 2> largest_intersection_sizes = {0, 0}; for (int dir = 0; dir < 2; dir++) { debug(dir); debug_arr(neighbours[dir], 0, (n << 1)); largest_intersection_sizes[dir] = largest_intersection_size(0, lengths[dir], 0, (n << 1), sorted_events[dir], neighbours[dir]); } debug(largest_intersection_sizes); cout << LL{1} * largest_intersection_sizes[0] * largest_intersection_sizes[1]; } int main() { speed_of_cin_and_cout; int test_cases_num = 1; // cin >> test_cases_num; for (int i = 1; i <= test_cases_num; i++) { local if (test_cases_num > 1) cerr << "Test #" << i << ":\n"; solve(); local if (test_cases_num > 1) cerr << "End of test #" << i << ".\n"; } 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 | // Author: Kamil Nizinski // NOLINT(legal/copyright) #ifdef LOCAL #ifdef COLOR #include "bits/cp_local_color.h" #else #include "bits/cp_local.h" #endif #else #include "bits/stdc++.h" #define debug_arr(arr_name, first, last) #define debug(...) #define cerr if (false) cerr #define speed_of_cin_and_cout ios_base::sync_with_stdio(0), cin.tie(0) #define local if (false) #endif #define ft first #define sd second #define psb push_back #define sz(a) (static_cast<int>((a).size())) using namespace std; // NOLINT(build/namespaces) typedef int64_t LL; typedef uint64_t LLU; typedef long double LD; typedef pair<int, int> PII; const int kMaxN = 500007; int largest_intersection_size(int start_dist, int end_dist, int p, int q, array<int, 2> *sorted_events, int *neighbours) { debug(p, q, sorted_events[p], sorted_events[q - 1]); debug(start_dist, end_dist); if (p == q) { debug(start_dist, end_dist); return end_dist - start_dist; } int r = neighbours[p]; debug(r, sorted_events[r]); if (p <= r && r < q) { cerr << "Double\n"; return max(largest_intersection_size(sorted_events[p][0], sorted_events[r][0], p + 1, r, sorted_events, neighbours), largest_intersection_size(sorted_events[r][0], end_dist + sorted_events[p][0] - start_dist, r, q, sorted_events, neighbours)); } else { cerr << "Single\n"; return max(sorted_events[p][0] - start_dist, largest_intersection_size(sorted_events[p][0], end_dist, p + 1, q, sorted_events, neighbours)); } } void solve() { int n; cin >> n; array<int, 2> lengths; for (int dir = 0; dir < 2; dir++) cin >> lengths[dir]; static array<int, 2> positions_of_pairs[2][kMaxN]; static array<int, 2> sorted_events[2][kMaxN << 1]; static int neighbours[2][kMaxN << 1]; for (int i = 0; i < n; i++) { int points[2][2]; for (int coor = 0; coor < 2; coor++) for (int dir = 0; dir < 2; dir++) cin >> points[dir][coor]; for (int dir = 0; dir < 2; dir++) { for (int coor = 0; coor < 2; coor++) sorted_events[dir][(i << 1) + coor] = {points[dir][coor], i}; positions_of_pairs[dir][i] = {-1, -1}; } } for (int dir = 0; dir < 2; dir++) { debug(dir); sort(sorted_events[dir], sorted_events[dir] + (n << 1)); debug_arr(sorted_events[dir], 0, (n << 1)); for (int i = 0; i < (n << 1); i++) { int idx = sorted_events[dir][i][1]; if (positions_of_pairs[dir][idx][0] == -1) positions_of_pairs[dir][idx][0] = i; else { positions_of_pairs[dir][idx][1] = i; for (int coor = 0; coor < 2; coor++) neighbours[dir][positions_of_pairs[dir][idx][coor]] = positions_of_pairs[dir][idx][1 - coor]; } } } array<int, 2> largest_intersection_sizes = {0, 0}; for (int dir = 0; dir < 2; dir++) { debug(dir); debug_arr(neighbours[dir], 0, (n << 1)); largest_intersection_sizes[dir] = largest_intersection_size(0, lengths[dir], 0, (n << 1), sorted_events[dir], neighbours[dir]); } debug(largest_intersection_sizes); cout << LL{1} * largest_intersection_sizes[0] * largest_intersection_sizes[1]; } int main() { speed_of_cin_and_cout; int test_cases_num = 1; // cin >> test_cases_num; for (int i = 1; i <= test_cases_num; i++) { local if (test_cases_num > 1) cerr << "Test #" << i << ":\n"; solve(); local if (test_cases_num > 1) cerr << "End of test #" << i << ".\n"; } return 0; } |