// 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; } |
English