// int main (void) { return 0; }
#define MUNDANE_ROUTINES__FOLDING__FOLD_SCOPE
#define ITERATIVE_MERGE_SORT__FOLDING__FOLD_SCOPE
#define BINARY_INDEXED_TREE__FOLDING__FOLD_SCOPE
#define ZOO_PROGRAM__FOLDING__FOLD_SCOPE
/* _ Each foldable “unit” to include all it needs; may be verified, defining only it, not the others, and building the whole file.
** _
** _ Possibly the one line main() needs to be uncommented, as well.
** _
** _ Break a long program, into its smaller parts, each doing its bit, while all working together, as well, in the end.
**
*/
#if defined(MUNDANE_ROUTINES__FOLDING__FOLD_SCOPE) /* imperative programming */
#include <stddef.h>
#include <string.h>
#include <inttypes.h>
size_t mundane_routines__size_t__log_2_ceiling (size_t n) {
/**
*** _ Given n ∈ ℤ, 1 ≤ n, it gives back k, k ∈ ℤ, 0 ≤ k, 2ᵏ⁻¹ < n ≤ 2ᵏ;
*** _
*** _ Given n ∈ ℤ, 0 = n, it gives back k, k = 0;
*** _
*** _ Tertium non datur, size_t being an unsigned integer type.
**/
size_t k = 0;
if (0 < n) {
size_t p = 0;
size_t x = 0;
p = 1;
x = 0;
while (x != n) {
if (0 != (n & p)) {
x |= p;
}
p = p + p;
k = k + 1;
}
if (0 == (n & (n - 1))) {
k -= 1;
}
}
return k;
}
size_t mundane_routines__size_t__no_wraparound_multiplication_or_zero (size_t a, size_t b) {
/** The arithmetic product of a and b if it may be hosted by a size_t, or else 0. */
return ((b == 0) ? 0 : (((SIZE_MAX / b) < a) ? 0 : (a * b)));
}
size_t mundane_routines__size_t__no_wraparound_addition_or_zero (size_t a, size_t b) {
/** The arithmetic sum of a and b if it may be hosted by a size_t, or else 0. */
return (((SIZE_MAX - b) < a) ? 0 : (a + b));
}
size_t mundane_routines__size_t__max2 (size_t a, size_t b) {
/** MAX {a, b}. */
return ((a < b) ? b : a);
}
#endif
#if defined(ITERATIVE_MERGE_SORT__FOLDING__FOLD_SCOPE) /* imperative programming */
#include <stddef.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
/* _ The much needed headers.
*/
#if !defined(MUNDANE_ROUTINES__FOLDING__FOLD_SCOPE)
size_t mundane_routines__size_t__no_wraparound_multiplication_or_zero (size_t a, size_t b) { return a * b; }
size_t mundane_routines__size_t__log_2_ceiling (size_t n) { return 1 + (n / 4); }
#endif
/* _ Local external dependency,
** _
** _ fillins for when one wants to verify the fold is almost self sufficient, like including all its headers, and everything,
** _
** _ everything except for a few routines included from outside, without including anything, when all is in one file, …
*/
#define ITERATIVE_MERGE_SORT__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__OPEN {
#define ITERATIVE_MERGE_SORT__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__CLOSE }
#define ITERATIVE_MERGE_SORT__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN ITERATIVE_MERGE_SORT__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
#define ITERATIVE_MERGE_SORT__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE ITERATIVE_MERGE_SORT__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__OPEN
/* _ un– fold –ing
*/
#define ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE 0
#define ITERATIVE_MERGE_SORT__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM 1
/** _ Trying to have as obvious as possible exit status values.
**/
struct iterative_merge_sort_data_type {
/**
*** _ Let’s do an iterative merge sort.
*** _
*** _ All the data we need, in one place.
*** _
*** _ No memory allocation, all should be put in place.
*** _
**** _ All to be put in place, knowning the convention.
**/
size_t number_of_elements;
/** _ How many elements we would be sorting ? */
size_t element_byte_size;
/** _ What is the element byte size ? */
void * element_array_itself;
/** _ The memory region where the elements are stored, in an array [ … ] */
void * auxiliary_array_itself;
/** _ The memory region where the elements may be merged, an auxiliary array [ … ] */
size_t ( * recursion_stack_itself ) [ 2 ];
/** _ Iterative recursion stack array whose elements are
** _
*** _ “the call stack frames” which would be used in the execution of a recursive implementation.
**/
size_t recursion_stack_its_size;
/** _ How many elements does the stack have ? */
int ( * comparison_function)(void const * element_j, void const * element_k);
/** _ How do we compare two elements ? [ … ] */
};
void iterative_merge_sort__merge_two_subarrays (struct iterative_merge_sort_data_type * merge_sort_data, size_t subarray_index_begin, size_t subarray_index_end) {
/* It may be seen that subarray_index_end − subarray_index_begin ≥ 2, by the way the caller does its recursion, calling into this routine. */
unsigned char ( * const elements_array_too ) = merge_sort_data->element_array_itself;
unsigned char const ( * const elements_array ) = merge_sort_data->element_array_itself;
unsigned char ( * const auxiliary_array ) = merge_sort_data->auxiliary_array_itself;
size_t const element_byte_size = merge_sort_data->element_byte_size;
int ( * comparison_function ) (void const * element_j, void const * element_k) = merge_sort_data->comparison_function;
size_t index_j = subarray_index_begin;
size_t const end_j = subarray_index_begin + (subarray_index_end - subarray_index_begin) / 2;
size_t index_k = end_j;
size_t const end_k = subarray_index_end;
size_t index_o = subarray_index_begin;
int comparison_result = 0;
while ((index_j < end_j) && (index_k < end_k)) {
comparison_result = comparison_function(elements_array + (index_j * element_byte_size), elements_array + (index_k * element_byte_size));
if (comparison_result <= 0) {
memcpy(auxiliary_array + (index_o * element_byte_size), elements_array + (index_j * element_byte_size), element_byte_size);
index_j += 1;
}
else {
memcpy(auxiliary_array + (index_o * element_byte_size), elements_array + (index_k * element_byte_size), element_byte_size);
index_k += 1;
}
index_o += 1;
}
if (index_j < end_j) {
memcpy(auxiliary_array + (index_o * element_byte_size), elements_array + (index_j * element_byte_size), (end_j - index_j) * element_byte_size);
}
if (index_k < end_k) {
memcpy(auxiliary_array + (index_o * element_byte_size), elements_array + (index_k * element_byte_size), (end_k - index_k) * element_byte_size);
}
memcpy(elements_array_too + (subarray_index_begin * element_byte_size),
auxiliary_array + (subarray_index_begin * element_byte_size),
(subarray_index_end - subarray_index_begin) * element_byte_size);
}
int iterative_merge_sort__sort_the_array_increasingly_by_comparison_function (struct iterative_merge_sort_data_type * merge_sort_data) {
/* Step is define and O(1) initialize O(1) variables local into the immediately outer block. */ {
ITERATIVE_MERGE_SORT__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
ITERATIVE_MERGE_SORT__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is verify that the provided number of elements and element byte size at least look valid. */ {
if (ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = merge_sort_data->number_of_elements;
size_t const element_byte_size = merge_sort_data->element_byte_size;
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ITERATIVE_MERGE_SORT__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is verify that the provided call stack seems to suffice for sorting the given array. */ {
if (ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = merge_sort_data->number_of_elements;
size_t const recursion_stack_size = merge_sort_data->recursion_stack_its_size;
size_t const auxiliary_value_0 = mundane_routines__size_t__log_2_ceiling(number_of_elements);
size_t const needed_stack_frames = mundane_routines__size_t__no_wraparound_addition_or_zero(auxiliary_value_0, 1);
if (recursion_stack_size < needed_stack_frames) {
exit_status = ITERATIVE_MERGE_SORT__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is sort the elements array, increasingly according to the given comparison function. */ {
if (ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = merge_sort_data->number_of_elements;
if (2 <= number_of_elements) {
size_t ( * const iterative_recursion_stack_itself ) [ 2 ] = merge_sort_data->recursion_stack_itself;
size_t iterative_recursion_stack_current_size = 1;
size_t iterative_recursion_stack_previous_size = 0;
size_t array_index_begin = 0;
size_t array_index_end = 0;
iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][0] = 0;
iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][1] = number_of_elements;
while (0 < iterative_recursion_stack_current_size) {
array_index_begin = iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][0];
array_index_end = iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][1];
if (iterative_recursion_stack_previous_size < iterative_recursion_stack_current_size) {
iterative_recursion_stack_previous_size = iterative_recursion_stack_current_size;
if (array_index_begin < (array_index_end - 1)) {
iterative_recursion_stack_current_size += 1;
iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][0] = array_index_begin;
iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][1] = array_index_begin + (array_index_end - array_index_begin) / 2;
}
else {
iterative_recursion_stack_current_size -= 1;
}
}
else {
iterative_recursion_stack_previous_size = iterative_recursion_stack_current_size;
if (array_index_begin == iterative_recursion_stack_itself[(iterative_recursion_stack_current_size + 1) - 1][0]) {
iterative_recursion_stack_current_size += 1;
iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][0] = array_index_begin + (array_index_end - array_index_begin) / 2;
iterative_recursion_stack_itself[iterative_recursion_stack_current_size - 1][1] = array_index_end;
}
else {
iterative_merge_sort__merge_two_subarrays(merge_sort_data, array_index_begin, array_index_end);
iterative_recursion_stack_current_size -= 1;
}
}
}
}
}
}
/* Step is pass the baton, informing the caller on the local status, “everything all right or not ?” */ {
return exit_status;
}
}
#endif
#if defined(BINARY_INDEXED_TREE__FOLDING__FOLD_SCOPE) /* imperative programming */
#include <inttypes.h>
#include <stddef.h>
void binary_indexed_tree__initialize_all_to_zero (uint32_t * array_B, size_t size_n) {
/**
*** _ A[j] := 0, for j going from 1, up to and including n, step +1.
**/
size_t index_j = 0;
index_j = 1;
while (index_j <= size_n) {
array_B[index_j - 1] = 0;
index_j += 1;
}
}
void binary_indexed_tree__point_update (uint32_t * array_B, size_t size_n, size_t index_j) {
/** _ A[1 … n], n ∈ ℤ, 1 ≤ n, (SIZE_MAX − n) ≤ n, 1 ≤ j ≤ n;
*** _
*** _ The point update is: “A[j] += 1”, updating array B which represents array A.
*** _
*** _ ∀ j ∈ ℤ, 1 ≤ n, ∃ s ∈ ℤ, 0 ≤ s, ∃ k ∈ ℤ, 0 ≤ k, so that j = s·2ᵏ⁺¹ + 2ᵏ.
*** _
*** _ B[1 … n], so that B[s·2ᵏ⁺¹ + 2ᵏ] = (∑ u ← s·2ᵏ⁺¹ + 1 … s·2ᵏ⁺¹ + 2ᵏ ∷ A[u]).
*** _
*** _ The program remembers only B, being possible to determine A, from B.
*** _
*** _ The program stores the value B[j], in array_B[j − 1], for j := 1, j ≤ n, step +1.
*** _
*** _ The value in size_n is n, and the value in index_j is j.
**/
while (index_j <= size_n) {
/* _ index_j: s·2ᵏ⁺¹ + 2ᵏ
** _
** _ (index_j & (index_j − 1): s·2ᵏ⁺¹
** _
** _ (index_j - (index_j & (index_j - 1))): 2ᵏ
*/
array_B[index_j - 1] += 1;
index_j = index_j + (index_j - (index_j & (index_j - 1)));
}
}
uint32_t binary_indexed_tree__prefix_query (uint32_t * array_B, size_t index_j) {
/** _ A[1 … n], n ∈ ℤ, 1 ≤ n, (SIZE_MAX − n) ≤ n; j ∈ ℤ, 1 ≤ j ≤ n;
*** _
*** _ B[1 … n], B[s·2ᵏ⁺¹ + 2ᵏ] = (∑ u ← s·2ᵏ⁺¹ + 1 … s·2ᵏ⁺¹ + 2ᵏ ∷ A[u]).
*** _
*** _ ∀ j ∈ ℤ, 1 ≤ n, ∃ s ∈ ℤ, 0 ≤ s, ∃ k ∈ ℤ, 0 ≤ k, so that j = s·2ᵏ⁺¹ + 2ᵏ.
*** _
*** _ The range query is “sum_s := ∑ p ← 1 … j ∷ A[p]”, having at hand just B[1 … n], not A[1 … n].
*** _
*** _ The implementation stores B[j], in array_B[j − 1], for j := 1, j ≤ n, step +1.
*** _
*** _ The value in index_j is j; j ≤ n, and n is not given, the program is expected to be correct.
**/
size_t sum_s = 0;
while (0 < index_j) {
sum_s = sum_s + array_B[index_j - 1];
index_j = index_j & (index_j - 1);
}
return sum_s;
}
uint32_t binary_indexed_tree__range_query (uint32_t * array_B, size_t index_from, size_t index_to) {
/** _ Returns (∑ j ← from … to ∷ A[j]) = (A[from] + A[from + 1] + … + A[to − 1] + A[to]).
*** _
*** _ A[1 … n], (SIZE_T − n) ≥ n, 1 ≤ from ≤ to ≤ n,
*** _
*** _ B[1 … n], B[s·2ᵏ⁺¹ + 2ᵏ] = (∑ u ← s·2ᵏ⁺¹ + 1 … s·2ᵏ⁺¹ + 2ᵏ ∷ A[u]),
*** _
*** _ B[j] is stored in array_B[j − 1], for j := 1, j ≤ n, step +1.
*** _
*** _ index_from: from, index_to: to.
**/
uint32_t const prefix_sum_from = binary_indexed_tree__prefix_query(array_B, index_from - 1);
uint32_t const prefix_sum_to = binary_indexed_tree__prefix_query(array_B, index_to);
return (prefix_sum_to - prefix_sum_from);
}
#endif
#if defined(ZOO_PROGRAM__FOLDING__FOLD_SCOPE) /* imperative programming */
#define ZOO_PROGRAM__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__OPEN {
#define ZOO_PROGRAM__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__CLOSE }
#define ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN ZOO_PROGRAM__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
#define ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE ZOO_PROGRAM__FOLDING__BLOCK_SCOPE_CURLY_BRACKETS__OPEN
#define ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE 0
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY 1
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE 2
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT 3
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T 4
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_UINT32_T 5
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM 6
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT 7
#define ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUTPUT_FILE 7
#define ZOO_PROGRAM__MACRO_CONSTANTS__MINIMUM_NUMBER_OF_POINTS 1
#define ZOO_PROGRAM__MACRO_CONSTANTS__MAXIMUM_NUMBER_OF_POINTS 16000
#define ZOO_PROGRAM__MACRO_CONSTANTS__MINIMUM_NUMBER_OF_RECTANGLES 1
#define ZOO_PROGRAM__MACRO_CONSTANTS__MAXIMUM_NUMBER_OF_RECTANGLES 100000
#define ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MIN_COORDINATE_VALUE -2000000000
#define ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MAX_COORDINATE_VALUE +2000000000
#define ZOO_PROGRAM__MACRO_CONSTANTS__LINE_BUFFER_ITS_CAPACITY 256
#include <inttypes.h>
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#if !defined(MUNDANE_ROUTINES__FOLDING__FOLD_SCOPE) /* local external dependency, the few mundane routines. */
size_t mundane_routines__size_t__no_wraparound_multiplication_or_zero (size_t a, size_t b) { return a * b; }
size_t mundane_routines__size_t__no_wraparound_addition_or_zero (size_t a, size_t b) { return a + b; }
size_t mundane_routines__size_t__log_2_ceiling (size_t n) { return 1 + (n / 4); }
size_t mundane_routines__size_t__max2 (size_t a, size_t b) { return ((a < b) ? b : a); }
#endif
#if !defined(ITERATIVE_MERGE_SORT__FOLDING__FOLD_SCOPE) /* local external dependency, the merge sort */
#define ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE 0
struct iterative_merge_sort_data_type {
size_t number_of_elements;
size_t element_byte_size;
void * element_array_itself;
void * auxiliary_array_itself;
size_t ( * recursion_stack_itself ) [ 2 ];
size_t recursion_stack_its_size;
int ( * comparison_function)(void const * element_j, void const * element_k);
};
int iterative_merge_sort__sort_the_array_increasingly_by_comparison_function (struct iterative_merge_sort_data * p) { (void) p; return 0; }
#endif
#if !defined(BINARY_INDEXED_TREE__FOLDING__FOLD_SCOPE) /* local external dependency, the binary indexed tree */
void binary_indexed_tree__initialize_all_to_zero (uint32_t * B, size_t n) { (void) B; (void) n; }
uint32_t binary_indexed_tree__range_query (uint32_t * B, size_t j, size_t k) { (void) B; (void) j; (void) k; return 0; }
void binary_indexed_tree__point_update (uint32_t * B, size_t n, size_t j) { (void) B; (void) n; (void) j; }
#endif
/* _ All together, each apart. */
struct vertical_coordinates_relabeling_entry {
/** _ An entry, or a record, for relabeling the y values of points P[j] and rectangles R[j].
*** _
*** _ Plan is to replace the coordinate values with their respective ranks in the ascending sorted order of themselves.
*** _
*** _ Each point P[j] contributes one entry in the array, an entry for its P[j].y value; n points to sort out.
*** _
*** _ Each rectangle R[j] contributes two entries, one for its R[j].y1 value, and another for its R[j].y2 value; m rectangles to sort out.
*** _
*** _ The sum total is n + 2·m coordinates to relabel, deriving for each such its compact y label amounting.
*** _
*** _ These new labels are elements of the following set [0, n + 2·m − 1] ∩ ℤ, understandingly.
**/
uint32_t y_value;
/** _ An initial Y coordinate value, simple as that.
***
**/
uint32_t j_object;
/** _ A j index, needing a little bit of decoding.
*** _
*** _ _ If j_object ∈ [0, n − 1] ∩ ℤ, then j := j_object − 0 is the identifying index of a point P[j], and y_value = P[j].y.
*** _ _
*** _ _ If j_object ∈ [n, n + m − 1] ∩ ℤ, then j := j_object − n is the identifying index of a rectangle R[j], and y_value ∈ {R[j].y1, R[j].y2}.
*** _ _
*** _ _ Tertium non datur, because we only had had points and rectangles to begin with, and we only encoded as much as we list above, from these objects.
*** _
*** _
**/
};
struct vertical_sweep_line_event {
/** _ The sweep line events, we are to sort these increasingly first on value, and second on j_object % 4.
*** _
*** _ A sweep line event object is of three types (1) E = (R[j].x1, 0 + 4·(m + j)), (2) E = (P[j].x, 1 + 4·j), and (3) E = (R[j].x2, 2 + 4·(m + j)).
*** _
*** _ The point is to sort so that sweeping the vertical lines in the order given by the sorted sequence gives the number of points intersecting rectangles.
**/
uint32_t x_value;
/** _ The horizontal coordinate value, the “on value” part, mentioned above.
***
**/
uint32_t j_object;
/** _ The object type and object identifying index part, detailed above, one of the 0 + 4·(m + j), 1 + 4·j, and 2 + 4·(m + j) values described above.
*** _
*** _ The left over part after dividing j_object by 4 is the object type, the 0 in “0 + 4·(m + j)”, the 1 in “1 + 4·j”, or the 2 in “2 + 4·(m + j)”.
*** _
*** _ The quotient after dividing j_object by 4 is the identifying index, after a bit of work, in the sense that one needs to subtract m from m + j to get to j.
**/
};
struct zoo_program__point {
/** _ A point. */
uint32_t point_x;
/** _ Its X coordinate. */
uint32_t point_y;
/** _ Its Y coordinate. */
};
struct zoo_program__rectangle {
/** _ A rectangle (x₁, y₁), (x₂, y₂), x₁ < x₂, y₁ < y₂. */
uint32_t rectangle_x1;
/** _ Its lower – left corner ’s X coordinate. */
uint32_t rectangle_y1;
/** _ Its lower – left corner ’s Y coordinate. */
uint32_t rectangle_x2;
/** _ Its upper – right corner ’s X coordinate. */
uint32_t rectangle_y2;
/** _ Its upper – right corner ’s Y coordinate. */
};
struct zoo_program__program_state {
/**
*** _ Everything which is used for solving the problem.
**/
FILE * input_file_itself;
/** _ What it says, nothing more, nothing less. */
char * line_buffer_itself;
/** _ Bounded I/O, why not. */
size_t line_buffer_its_capacity;
/** _ How many bytes ? */
size_t number_of_points_itself;
/** _ This one, is the number n, the number of points. */
size_t number_of_rectangles_itself;
/** _ This one is the number m, the number of rectangles. */
struct zoo_program__point * points_array_itself;
/** _ This one, the points, the lot of them. */
struct zoo_program__rectangle * rectangles_array_itself;
/** _ This one, the rectangles, the lot of them. */
size_t merge_sort_arrays_common_size_itself;
/**
*** _ What is the size when the program would use the merge arrays ?
*** _
*** _ The common size of these arrays is the max size of the binary tree, as well.
*** _
*** _ Size as in the number of elements, not as in the number of bytes.
**/
void * merge_sort_elements_array_itself;
/**
*** _ The elements array to be sorted by merge sort.
*** _
*** _ It is just the storage able to host (n + 2·m) elements.
*** _
*** _ The element type may be vertical_coordinates_relabeling_entry.
*** _
*** _ The element type may be vertical_sweep_line_event.
*** _
*** _ We just sort both, using the same storage.
**/
void * merge_sort_auxiliary_array_itself;
/**
*** _ The auxiliary array, providing space to do the merging.
**/
size_t ( * merge_sort_recursion_stack_itself ) [ 2 ];
/** _ We do our iterative recursion using this array as our recursion stack. */
size_t merge_sort_recursion_stack_its_size;
/** _ How many elements, the stack ? */
uint32_t * binary_indexed_tree_itself;
/**
*** _ After relabeling, point updates and range queries.
*** _
*** _ If P[j] is any point, then P[j].y ∈ [0, n + 2·m − 1] ∩ ℤ, after relabeling.
*** _
*** _ If R[j] is any rectangle, then {R[j].y1, R[j].y2} ⊆ [0, n + 2·m − 1] ∩ ℤ, after relabeling.
*** _
*** _ A[0 … n + 2·m − 1] an array; point update: A[P[j].y] += 1, range query: ∑ j := R[j].y1 … R[j].y2 ∷ A[j].
*** _
*** _ The array A only implicitly and or conceptually; the program works with its corresponding binary indexed tree.
**/
size_t binary_indexed_tree_its_size;
/**
*** _ The size of the array is not this number, but instead is the value in merge_sort_arrays_common_size_itself.
*** _
*** _ The size of the array is how many elements were allocated for the array itself.
*** _
*** _ The value of binary_indexed_tree_its_size data member is the number 1 + Y_max.
*** _
*** _ Our indexing of Y coordinates makes y ∈ [0 … Y_max] ∩ ℤ, whence 1 + Y_max.
*** _
*** _ 1 + Y_max ≤ merge_sort_arrays_common_size_itself, by design.
*** _
*** _ Equality is possible, as is using less space.
**/
uint32_t * answers_array_itself;
/**
*** _ For each rectangle, the ♯ of points in it, or on its border.
**/
FILE * output_file_itself;
/** It is what the name says it is, nothing more, nothing less. */
};
int zoo_program__allocate_all_the_required_resources_up_front_reading_the_problem_from_the_input_file (struct zoo_program__program_state * * program_state_receptacle) {
/* Step is define and O(1) initialize a handful of variables local into the immediately enclosing outer block scope. */ {
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
struct zoo_program__program_state * program_state_itself = NULL;
FILE * input_file_itself = NULL;
char * line_buffer_itself = NULL;
size_t line_buffer_its_capacity = 0;
size_t number_of_points_itself = 0;
size_t number_of_rectangles_itself = 0;
struct zoo_program__point * points_array_itself = NULL;
struct zoo_program__rectangle * rectangles_array_itself = NULL;
size_t merge_sort_arrays_common_size_itself = 0;
void * merge_sort_elements_array_itself = NULL;
void * merge_sort_auxiliary_array_itself = NULL;
void * merge_sort_recursion_stack_itself = NULL;
size_t merge_sort_recursion_stack_its_size = 0;
void * binary_indexed_tree_itself = NULL;
void * answers_array_itself = NULL;
FILE * output_file_itself = NULL;
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is verify that the line buffer macro constant value may fit in both size_t and int, thus being safe to cast between this types, this value. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if ( (ZOO_PROGRAM__MACRO_CONSTANTS__LINE_BUFFER_ITS_CAPACITY < 0) ||
(INT_MAX < ZOO_PROGRAM__MACRO_CONSTANTS__LINE_BUFFER_ITS_CAPACITY) ||
(SIZE_MAX < ZOO_PROGRAM__MACRO_CONSTANTS__LINE_BUFFER_ITS_CAPACITY) ) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT;
}
}
}
/* Step is verify that uint32_t is sufficient for representing points and rectangles corners ’ coordinates. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int64_t const min_coordinate_value = ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MIN_COORDINATE_VALUE;
int64_t const max_coordinate_value = ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MAX_COORDINATE_VALUE;
if ((max_coordinate_value < 0) || (0 < min_coordinate_value)) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT;
}
else {
if (INT64_MIN == min_coordinate_value) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT;
}
else {
uint64_t const a = ((uint64_t) (-min_coordinate_value));
uint64_t const b = ((uint64_t) max_coordinate_value );
uint64_t const c = ((UINT64_MAX - b) < a ? 0 : (a + b));
if (0 == c) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
else {
if (UINT32_MAX < c) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT;
}
else {
/* _ All is fine, carry on.
** _
** _ The checks are to make sure that uint32_t may be used to store y − c_min, x − c_min, as uint32_t values.
** _
** _ c_min := ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MIN_COORDINATE_VALUE, the minimum coordinate value.
** _
** _ Basically translate all coordinates by − c_min, a positive integer, to work with uint32_t, more relaxing with unsigned values, somehow.
**
*/
}
}
}
}
}
}
/* Step is acquire the program state object itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_bytes = sizeof(struct zoo_program__program_state);
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
program_state_itself = pointer_p;
}
}
}
/* Step is acquire the input FILE object itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * const file_f = fopen("zoo.in", "r");
if (NULL == file_f) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
input_file_itself = file_f;
}
}
}
/* Step is acquire the line buffer itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_bytes = ZOO_PROGRAM__MACRO_CONSTANTS__LINE_BUFFER_ITS_CAPACITY;
if (number_of_bytes < 24) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM; /* Letʹs have a larger line buffer, mkay. */
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
line_buffer_itself = pointer_p;
line_buffer_its_capacity = number_of_bytes;
}
}
}
}
/* Step is read the number of points from the input file itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_n = 0;
char * buff = NULL;
buff = fgets(line_buffer_itself, (/* CAST_TO */ (int) /* from size_t */ line_buffer_its_capacity), input_file_itself);
if (NULL == buff) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
size_t const len = strlen(buff);
if ((buff != line_buffer_itself) || (len <= 0) || (buff[len - 1] != '\n')) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
int s_code = 0;
s_code = sscanf(buff, "%zu", &number_n);
if (1 != s_code) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
size_t const min_n = ZOO_PROGRAM__MACRO_CONSTANTS__MINIMUM_NUMBER_OF_POINTS;
size_t const max_n = ZOO_PROGRAM__MACRO_CONSTANTS__MAXIMUM_NUMBER_OF_POINTS;
if ((number_n < min_n) || (max_n < number_n)) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT;
}
else {
number_of_points_itself = number_n;
}
}
}
}
}
}
/* Step is acquire the points array itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_points_itself;
size_t const element_byte_size = sizeof(struct zoo_program__point);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
points_array_itself = pointer_p;
}
}
}
}
/* Step is read all the points from the input file itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int64_t minimum_coordinate_value = ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MIN_COORDINATE_VALUE;
int64_t maximum_coordinate_value = ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MAX_COORDINATE_VALUE;
size_t point_index = 0;
int64_t x_ival = 0;
int64_t y_ival = 0;
char * buff = NULL;
size_t len = 0;
int s_code = 0;
point_index = 0;
while ((ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (point_index < number_of_points_itself)) {
buff = fgets(line_buffer_itself, (/* CAST_TO */ (int) /* from size_t */ line_buffer_its_capacity), input_file_itself);
if (NULL == buff) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
len = strlen(buff);
if ((buff != line_buffer_itself) || (len <= 0) || (buff[len - 1] != '\n')) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
s_code = sscanf(buff, "%" SCNi64 " " "%" SCNi64, &x_ival, &y_ival);
if (2 != s_code) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
if ((x_ival < minimum_coordinate_value) || (maximum_coordinate_value < x_ival) ||
(y_ival < minimum_coordinate_value) || (maximum_coordinate_value < y_ival)) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT;
}
else {
points_array_itself[point_index].point_x = (/* CAST_TO */ (uint32_t) /* from int64_t */ (x_ival - minimum_coordinate_value));
points_array_itself[point_index].point_y = (/* CAST_TO */ (uint32_t) /* from int64_t */ (y_ival - minimum_coordinate_value));
point_index += 1;
}
}
}
}
}
}
}
/* Step is read the number of rectangles from the input file itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_m = 0;
char * buff = NULL;
buff = fgets(line_buffer_itself, (/* CAST_TO */ (int) /* from size_t */ line_buffer_its_capacity), input_file_itself);
if (NULL == buff) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
size_t const len = strlen(buff);
if ((buff != line_buffer_itself) || (len <= 0) || (buff[len - 1] != '\n')) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
int s_code = 0;
s_code = sscanf(buff, "%zu", &number_m);
if (1 != s_code) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
size_t const min_m = ZOO_PROGRAM__MACRO_CONSTANTS__MINIMUM_NUMBER_OF_RECTANGLES;
size_t const max_m = ZOO_PROGRAM__MACRO_CONSTANTS__MAXIMUM_NUMBER_OF_RECTANGLES;
if ((number_m < min_m) || (max_m < number_m)) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT;
}
else {
number_of_rectangles_itself = number_m;
}
}
}
}
}
}
/* Step is acquire the rectangles array itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_rectangles_itself;
size_t const element_byte_size = sizeof(struct zoo_program__rectangle);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
rectangles_array_itself = pointer_p;
}
}
}
}
/* Step is read all the rectangles from the input file itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int64_t minimum_coordinate_value = ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MIN_COORDINATE_VALUE;
int64_t maximum_coordinate_value = ZOO_PROGRAM__MACRO_CONSTANTS__POINTS_MAX_COORDINATE_VALUE;
size_t rectangle_index = 0;
int64_t x1_ival = 0;
int64_t y1_ival = 0;
int64_t x2_ival = 0;
int64_t y2_ival = 0;
char * buff = NULL;
size_t len = 0;
int s_code = 0;
rectangle_index = 0;
while ((ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (rectangle_index < number_of_rectangles_itself)) {
buff = fgets(line_buffer_itself, (/* CAST_TO */ (int) /* from size_t */ line_buffer_its_capacity), input_file_itself);
if (NULL == buff) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
len = strlen(buff);
if ((buff != line_buffer_itself) || (len <= 0) || (buff[len - 1] != '\n')) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
s_code = sscanf(buff, "%" SCNi64 " " "%" SCNi64 " " "%" SCNi64 " " "%" SCNi64, &x1_ival, &y1_ival, &x2_ival, &y2_ival);
if (4 != s_code) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
if ((x1_ival < minimum_coordinate_value) || (maximum_coordinate_value < x1_ival) ||
(y1_ival < minimum_coordinate_value) || (maximum_coordinate_value < y1_ival) ||
(x2_ival < minimum_coordinate_value) || (maximum_coordinate_value < x2_ival) ||
(y2_ival < minimum_coordinate_value) || (maximum_coordinate_value < y2_ival)) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INVALID_INPUT;
}
else {
rectangles_array_itself[rectangle_index].rectangle_x1 = (/* CAST_TO */ (uint32_t) /* from int64_t */ (x1_ival - minimum_coordinate_value));
rectangles_array_itself[rectangle_index].rectangle_y1 = (/* CAST_TO */ (uint32_t) /* from int64_t */ (y1_ival - minimum_coordinate_value));
rectangles_array_itself[rectangle_index].rectangle_x2 = (/* CAST_TO */ (uint32_t) /* from int64_t */ (x2_ival - minimum_coordinate_value));
rectangles_array_itself[rectangle_index].rectangle_y2 = (/* CAST_TO */ (uint32_t) /* from int64_t */ (y2_ival - minimum_coordinate_value));
rectangle_index += 1;
}
}
}
}
}
}
}
/* Step is acquire the common size of the merge sort arrays. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
/* _ Every rectangle R gets to have precisely 2 elements in each merge – sort array, on element for its R.x1 value, and other element for its R.x2 value.
** _
** _ Every point P get to have precisely 1 element in each merge — sort array, an element for its P.x value.
** _
** _ For n points and m rectagles, we need n + 2·m sized merge – sort arrays.
*/
size_t const auxiliary_value_1 = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_rectangles_itself, 2);
size_t const number_of_elements = mundane_routines__size_t__no_wraparound_addition_or_zero(auxiliary_value_1, number_of_points_itself);
if (0 == number_of_elements) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
merge_sort_arrays_common_size_itself = number_of_elements;
}
}
}
/* Step is acquire the assurance the binary indexed binary tree operations will be well behaved, no unsigned integer wrap arounds. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
/*
** _ ’member the “A[1 … n + 2·m] an array; point update: A[P[j].y] += 1, range query: ∑ j := R[j].y1 … R[j].y2 ∷ A[j]” mentioned above ?
** _
** _ Let’s not use array A, directly, but instead its binary indexed tree array, say, B [ … ]
** _
** _ [ … ] when operating on this array B, better not be possible we wrap around our index j, [ … ]
** _
** _ [ … ] the condition verified here are included simply to prevent this potential wrap around [ … ]
*/
size_t array_a_size_upper_bound = merge_sort_arrays_common_size_itself;
if ((SIZE_MAX - array_a_size_upper_bound) < array_a_size_upper_bound) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT;
}
}
}
/* Step is acquire the merge sort elements array itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = merge_sort_arrays_common_size_itself;
size_t const element_byte_size_1 = sizeof(struct vertical_coordinates_relabeling_entry);
size_t const element_byte_size_2 = sizeof(struct vertical_sweep_line_event);
size_t const element_byte_size = mundane_routines__size_t__max2(element_byte_size_1, element_byte_size_2);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
merge_sort_elements_array_itself = pointer_p;
}
}
}
}
/* Step is acquire the merge sort auxiliary array itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = merge_sort_arrays_common_size_itself;
size_t const element_byte_size_1 = sizeof(struct vertical_coordinates_relabeling_entry);
size_t const element_byte_size_2 = sizeof(struct vertical_sweep_line_event);
size_t const element_byte_size = mundane_routines__size_t__max2(element_byte_size_1, element_byte_size_2);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
merge_sort_auxiliary_array_itself = pointer_p;
}
}
}
}
/* Step is acquire the merge sort iterative recursion stack array itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const auxiliary_value_0 = mundane_routines__size_t__log_2_ceiling(merge_sort_arrays_common_size_itself);
size_t const number_of_elements = mundane_routines__size_t__no_wraparound_addition_or_zero(auxiliary_value_0, 1);
size_t const element_byte_size = sizeof(size_t[2]);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
merge_sort_recursion_stack_itself = pointer_p;
merge_sort_recursion_stack_its_size = number_of_elements;
}
}
}
}
/* Step is acquire the binary indexed tree itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (UINT32_MAX < merge_sort_arrays_common_size_itself) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_UINT32_T;
}
else {
size_t const number_of_elements = merge_sort_arrays_common_size_itself;
size_t const element_byte_size = sizeof(uint32_t);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
binary_indexed_tree_itself = pointer_p;
}
}
}
}
}
/* Step is acquire the answers array itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (UINT32_MAX < number_of_points_itself) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_UINT32_T;
}
else {
size_t const number_of_elements = number_of_rectangles_itself;
size_t const element_byte_size = sizeof(uint32_t);
size_t const number_of_bytes = mundane_routines__size_t__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__TOO_NARROW_SIZE_T;
}
else {
void ( * const pointer_p ) = malloc(number_of_bytes);
if (NULL == pointer_p) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUT_OF_MEMORY;
}
else {
answers_array_itself = pointer_p;
}
}
}
}
}
/* Step is acquire the output file itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * const file_g = fopen("zoo.out", "w");
if (NULL == file_g) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUTPUT_FILE;
}
else {
output_file_itself = file_g;
}
}
}
/* Step is pass the baton. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
program_state_itself->input_file_itself = input_file_itself;
program_state_itself->line_buffer_itself = line_buffer_itself;
program_state_itself->line_buffer_its_capacity = line_buffer_its_capacity;
program_state_itself->number_of_points_itself = number_of_points_itself;
program_state_itself->number_of_rectangles_itself = number_of_rectangles_itself;
program_state_itself->points_array_itself = points_array_itself;
program_state_itself->rectangles_array_itself = rectangles_array_itself;
program_state_itself->merge_sort_arrays_common_size_itself = merge_sort_arrays_common_size_itself;
program_state_itself->merge_sort_elements_array_itself = merge_sort_elements_array_itself;
program_state_itself->merge_sort_auxiliary_array_itself = merge_sort_auxiliary_array_itself;
program_state_itself->merge_sort_recursion_stack_itself = merge_sort_recursion_stack_itself;
program_state_itself->merge_sort_recursion_stack_its_size = merge_sort_recursion_stack_its_size;
program_state_itself->binary_indexed_tree_itself = binary_indexed_tree_itself;
program_state_itself->binary_indexed_tree_its_size = 0;
program_state_itself->answers_array_itself = answers_array_itself;
program_state_itself->output_file_itself = output_file_itself;
*program_state_receptacle = program_state_itself;
}
else {
if (NULL != output_file_itself) {
int s_code = fclose(output_file_itself);
if (0 != s_code) {
perror("output file");
}
}
if (NULL != answers_array_itself) {
free(answers_array_itself);
answers_array_itself = NULL;
}
if (NULL != binary_indexed_tree_itself) {
free(binary_indexed_tree_itself);
binary_indexed_tree_itself = NULL;
}
if (NULL != merge_sort_recursion_stack_itself) {
free(merge_sort_recursion_stack_itself);
merge_sort_recursion_stack_itself = NULL;
merge_sort_recursion_stack_its_size = 0;
}
if (NULL != merge_sort_auxiliary_array_itself) {
free(merge_sort_auxiliary_array_itself);
merge_sort_auxiliary_array_itself = NULL;
}
if (NULL != merge_sort_elements_array_itself) {
free(merge_sort_elements_array_itself);
merge_sort_elements_array_itself = NULL;
merge_sort_arrays_common_size_itself = 0;
}
if (NULL != rectangles_array_itself) {
free(rectangles_array_itself);
rectangles_array_itself = NULL;
}
if (NULL != points_array_itself) {
free(points_array_itself);
points_array_itself = NULL;
}
number_of_points_itself = 0;
number_of_rectangles_itself = 0;
if (NULL != line_buffer_itself) {
free(line_buffer_itself);
line_buffer_itself = NULL;
line_buffer_its_capacity = 0;
}
if (NULL != input_file_itself) {
int const c_code = fclose(input_file_itself);
input_file_itself = NULL;
if (0 != c_code) {
perror("input file");
}
}
if (NULL != program_state_itself) {
free(program_state_itself);
program_state_itself = NULL;
}
}
return exit_status;
}
}
int zoo_program__compare_two_vertical_coordinates_relabeling_entries (void const * entry_yj, void const * entry_yk) {
uint32_t const yj = (/* CAST_TO */ (struct vertical_coordinates_relabeling_entry const *) /* from (void const *) */ entry_yj)->y_value;
uint32_t const yk = (/* CAST_TO */ (struct vertical_coordinates_relabeling_entry const *) /* from (void const *) */ entry_yk)->y_value;
return ((yj < yk) ? (-1) : (((yj > yk) ? (+1) : (0))));
}
int zoo_program__perform_one_change_of_variables_for_vertical_coordinates (struct zoo_program__program_state * program_state_itself) {
/* Step is save a few words on what this routine is all about and what it is doing when called. */ {
/** _ This routine replaces each vertical coordinate with its position in the sorted sequence of vertical coordinates, not counting duplicates.
*** _
*** _ It patches the Y coordinates, so that when passing them into the segment tree operations the segment tree could have an initial segment not too large.
*** _
*** _ This Y value to Y’s position in the sorted order has the essential property that VALUE[Y] < VALUE[Y'] ⇐⇒ INDEX[Y] < INDEX[Y'].
**/
}
/* Step is define and O(1) initialize O(1) variables local into the immediately enclosing outer block. */ {
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
size_t maximum_vertical_coordinate_value = 0;
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is prepare an array containing Y coordinates, each coordinate accompanied by satelite data encoding where the respective coordinate came from. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_points = program_state_itself->number_of_points_itself;
struct zoo_program__point * points_array_itself = program_state_itself->points_array_itself;
size_t const number_of_rectangles = program_state_itself->number_of_rectangles_itself;
struct zoo_program__rectangle * rectangles_array_itself = program_state_itself->rectangles_array_itself;
struct vertical_coordinates_relabeling_entry * relabeling_entries_array_itself = program_state_itself->merge_sort_elements_array_itself;
size_t point_index = 0;
size_t rectangle_index = 0;
size_t relabeling_entry_index = 0;
point_index = 0;
while (point_index < number_of_points) {
relabeling_entries_array_itself[relabeling_entry_index].y_value = points_array_itself[point_index].point_y;
relabeling_entries_array_itself[relabeling_entry_index].j_object = 1 + 4 * point_index;
relabeling_entry_index += 1;
point_index += 1;
}
rectangle_index = 0;
while (rectangle_index < number_of_rectangles) {
relabeling_entries_array_itself[relabeling_entry_index].y_value = rectangles_array_itself[rectangle_index].rectangle_y1;
relabeling_entries_array_itself[relabeling_entry_index].j_object = 0 + 4 * rectangle_index;
relabeling_entry_index += 1;
relabeling_entries_array_itself[relabeling_entry_index].y_value = rectangles_array_itself[rectangle_index].rectangle_y2;
relabeling_entries_array_itself[relabeling_entry_index].j_object = 2 + 4 * rectangle_index;
relabeling_entry_index += 1;
rectangle_index += 1;
}
if (relabeling_entry_index != program_state_itself->merge_sort_arrays_common_size_itself) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is sort the array containing Y coordinates, each coordinate accompanied by satelite data encoding where the respective coordinate came from. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
struct iterative_merge_sort_data_type merge_sort_data_object;
size_t const number_of_elements = program_state_itself->merge_sort_arrays_common_size_itself;
size_t const element_byte_size = sizeof(struct vertical_coordinates_relabeling_entry);
struct vertical_coordinates_relabeling_entry ( * const element_array_itself ) = program_state_itself->merge_sort_elements_array_itself;
struct vertical_coordinates_relabeling_entry ( * const auxiliary_array_itself ) = program_state_itself->merge_sort_auxiliary_array_itself;
size_t ( * recursion_stack_itself ) [ 2 ] = program_state_itself->merge_sort_recursion_stack_itself;
size_t const recursion_stack_its_size = program_state_itself->merge_sort_recursion_stack_its_size;
int ( * comparison_function)(void const * /* element_j */, void const * /* element_k */ ) = &zoo_program__compare_two_vertical_coordinates_relabeling_entries;
int exit_status_too = 0;
merge_sort_data_object.number_of_elements = number_of_elements;
merge_sort_data_object.element_byte_size = element_byte_size;
merge_sort_data_object.element_array_itself = element_array_itself;
merge_sort_data_object.auxiliary_array_itself = auxiliary_array_itself;
merge_sort_data_object.recursion_stack_itself = recursion_stack_itself;
merge_sort_data_object.recursion_stack_its_size = recursion_stack_its_size;
merge_sort_data_object.comparison_function = comparison_function;
exit_status_too = iterative_merge_sort__sort_the_array_increasingly_by_comparison_function(&merge_sort_data_object);
if (ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is patch the vertical coordinates wherever they may be hosted, be it in a point, or be it in a rectangle. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
/*
** _ Relabeling starts at y = 1, because later on the program is updates and queries a binary indexed tree, in which indices go from 1 up to its size.
*/
size_t const number_of_entries = program_state_itself->merge_sort_arrays_common_size_itself;
struct vertical_coordinates_relabeling_entry ( * const relabeling_entries_array_itself ) = program_state_itself->merge_sort_elements_array_itself;
struct zoo_program__point ( * const points_array_itself ) = program_state_itself->points_array_itself;
struct zoo_program__rectangle ( * const rectangles_array_itself ) = program_state_itself->rectangles_array_itself;
size_t entry_index = 0;
size_t last_y_value = 0;
size_t current_y_value = 0;
size_t current_j_object = 0;
size_t current_j_index = 0;
size_t current_j_type = 0;
size_t y_rank = 0;
y_rank = 1;
entry_index = 0;
while ((ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (entry_index < number_of_entries)) {
current_y_value = relabeling_entries_array_itself[entry_index].y_value;
if (0 < entry_index) {
if (current_y_value < last_y_value) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
else {
if (last_y_value < current_y_value) {
y_rank += 1;
}
last_y_value = current_y_value;
}
}
else {
last_y_value = current_y_value;
}
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
current_j_object = relabeling_entries_array_itself[entry_index].j_object;
current_j_index = current_j_object / 4;
current_j_type = current_j_object % 4;
if (0 == current_j_type) {
rectangles_array_itself[current_j_index].rectangle_y1 = y_rank;
}
if (2 == current_j_type) {
rectangles_array_itself[current_j_index].rectangle_y2 = y_rank;
}
if (1 == current_j_type) {
points_array_itself[current_j_index].point_y = y_rank;
}
if (2 < current_j_type) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
else {
entry_index += 1;
}
}
}
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
maximum_vertical_coordinate_value = y_rank;
}
}
}
/* Step is pass the baton, assigning the size of the binary indexed tree to count points in rectangles, the maximum vertical coordinate value. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
program_state_itself->binary_indexed_tree_its_size = maximum_vertical_coordinate_value;
}
return exit_status;
}
}
int zoo_program__compare_two_vertical_sweep_line_events (void const * event_xj, void const * event_xk) {
uint32_t const x_j = ((/* CAST_TO */ (struct vertical_sweep_line_event const *) /* from (void const *) */ event_xj)->x_value); /* x_ prefix for horizontal coordinate */
uint32_t const x_k = ((/* CAST_TO */ (struct vertical_sweep_line_event const *) /* from (void const *) */ event_xk)->x_value);
uint32_t const t_j = ((/* CAST_TO */ (struct vertical_sweep_line_event const *) /* from (void const *) */ event_xj)->j_object) % 4; /* t_ prefix for object type */
uint32_t const t_k = ((/* CAST_TO */ (struct vertical_sweep_line_event const *) /* from (void const *) */ event_xk)->j_object) % 4;
return ((x_j != x_k) ? ((x_j < x_k) ? (-1) : (+1)) : ((t_j == t_k) ? (0) : ((t_j < t_k) ? (-1) : (+1))));
}
int zoo_program__sort_the_vertical_sweep_line_records_preparing_for_point_updates_and_range_queries (struct zoo_program__program_state * program_state_itself) {
/* Step is save a few words on the processing described by this routine. */ {
/**
*** _ S[0 … n + 2·m − 1] the array to contain at most n + 2·m “vertical sweep line records”.
*** _
*** _ For j := 0 … n, S[j] := (P[j].x, 1 + 4·j).
*** _
*** _ For j := 0 … m, S[n + 2·j + 0] := (R[j].x1, 0 + 4·j), S[n + 2·j + 1] := (R[j].x2, 2 + 4·j).
*** _
*** _ Sort S[0 … n + 2·m − 1], increasingly first of S[j][0], second on S[j][1] % 4.
*** _
*** _ All this to perform point updates and range queries, finding the ♯ of points in rectangle.
*** _
*** _ This routine precomputes the S[0 … n + 2·m − 1], nothing more, nothing less.
***
**/
}
/* Step is define and O(1) initialize O(1) variables local into the immediately enclosing lexical block scope. */ {
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is prepare an array containing X coordinates, each such joined by satelite data encoding where the coordinate is a part in the full object. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_points = program_state_itself->number_of_points_itself;
struct zoo_program__point * points_array_itself = program_state_itself->points_array_itself;
size_t const number_of_rectangles = program_state_itself->number_of_rectangles_itself;
struct zoo_program__rectangle * rectangles_array_itself = program_state_itself->rectangles_array_itself;
struct vertical_sweep_line_event * vertical_sweep_line_events_array_itself = program_state_itself->merge_sort_elements_array_itself;
size_t point_index = 0;
size_t rectangle_index = 0;
size_t sweep_line_event_index = 0;
point_index = 0;
while (point_index < number_of_points) {
vertical_sweep_line_events_array_itself[sweep_line_event_index].x_value = points_array_itself[point_index].point_x;
vertical_sweep_line_events_array_itself[sweep_line_event_index].j_object = 1 + 4 * point_index;
sweep_line_event_index += 1;
point_index += 1;
}
rectangle_index = 0;
while (rectangle_index < number_of_rectangles) {
vertical_sweep_line_events_array_itself[sweep_line_event_index].x_value = rectangles_array_itself[rectangle_index].rectangle_x1;
vertical_sweep_line_events_array_itself[sweep_line_event_index].j_object = 0 + 4 * rectangle_index;
sweep_line_event_index += 1;
vertical_sweep_line_events_array_itself[sweep_line_event_index].x_value = rectangles_array_itself[rectangle_index].rectangle_x2;
vertical_sweep_line_events_array_itself[sweep_line_event_index].j_object = 2 + 4 * rectangle_index;
sweep_line_event_index += 1;
rectangle_index += 1;
}
if (sweep_line_event_index != program_state_itself->merge_sort_arrays_common_size_itself) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is sort the array containing X coordinates, such way to make the point updates and range queries give ”♯ points in rectangle” results. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = program_state_itself->merge_sort_arrays_common_size_itself;
size_t const element_byte_size = sizeof(struct vertical_sweep_line_event);
struct iterative_merge_sort_data_type merge_sort_data_object;
struct vertical_sweep_line_event ( * const element_array_itself ) = program_state_itself->merge_sort_elements_array_itself;
struct vertical_sweep_line_event ( * const auxiliary_array_itself ) = program_state_itself->merge_sort_auxiliary_array_itself;
size_t ( * recursion_stack_itself ) [ 2 ] = program_state_itself->merge_sort_recursion_stack_itself;
size_t const recursion_stack_its_size = program_state_itself->merge_sort_recursion_stack_its_size;
int ( * comparison_function)(void const * /* element_j */, void const * /* element_k */ ) = &zoo_program__compare_two_vertical_sweep_line_events;
int exit_status_too = 0;
merge_sort_data_object.number_of_elements = number_of_elements;
merge_sort_data_object.element_byte_size = element_byte_size;
merge_sort_data_object.element_array_itself = element_array_itself;
merge_sort_data_object.auxiliary_array_itself = auxiliary_array_itself;
merge_sort_data_object.recursion_stack_itself = recursion_stack_itself;
merge_sort_data_object.recursion_stack_its_size = recursion_stack_its_size;
merge_sort_data_object.comparison_function = comparison_function;
exit_status_too = iterative_merge_sort__sort_the_array_increasingly_by_comparison_function(&merge_sort_data_object);
if (ITERATIVE_MERGE_SORT__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
/* Step is pass the baton. */ {
return exit_status;
}
}
int zoo_program__move_the_vertical_sweep_line_left_to_right_solving_all_the_queries_finding_all_the_answers (struct zoo_program__program_state * program_state_itself) {
/* Step is define and O(1) initialize O(1) variables local into the immediately enclosing lexical block scope. */ {
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is define initialize the binary indexed tree to zero. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
uint32_t ( * const binary_indexed_tree_itself ) = program_state_itself->binary_indexed_tree_itself;
uint32_t const binary_indexed_tree_its_size = program_state_itself->binary_indexed_tree_its_size;
binary_indexed_tree__initialize_all_to_zero(binary_indexed_tree_itself, binary_indexed_tree_its_size);
}
}
/* Step is solve all queries, by doing a vertical sweep, doing point updates of vertical coordinates and range queries. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
uint32_t ( * const answers_array_itself ) = program_state_itself->answers_array_itself;
uint32_t ( * const binary_indexed_tree_itself ) = program_state_itself->binary_indexed_tree_itself;
size_t const binary_indexed_tree_its_size = program_state_itself->binary_indexed_tree_its_size;
struct zoo_program__point * points_array_itself = program_state_itself->points_array_itself;
struct zoo_program__rectangle * rectangles_array_itself = program_state_itself->rectangles_array_itself;
struct vertical_sweep_line_event * vertical_sweep_line_events_array_itself = program_state_itself->merge_sort_elements_array_itself;
size_t const number_of_vertical_sweep_line_events = program_state_itself->merge_sort_arrays_common_size_itself;
size_t vertical_sweep_line_event_index = 0;
size_t j_object = 0;
size_t j_index = 0;
size_t j_type = 0;
struct zoo_program__point * point_P = NULL;
struct zoo_program__rectangle * rectangle_R = NULL;
size_t range_query_answer = 0;
vertical_sweep_line_event_index = 0;
while ((ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (vertical_sweep_line_event_index < number_of_vertical_sweep_line_events)) {
j_object = vertical_sweep_line_events_array_itself[vertical_sweep_line_event_index].j_object;
j_index = j_object / 4;
j_type = j_object % 4;
if (0 == j_type) {
rectangle_R = &(rectangles_array_itself[j_index]);
range_query_answer = binary_indexed_tree__range_query(binary_indexed_tree_itself, rectangle_R->rectangle_y1, rectangle_R->rectangle_y2);
answers_array_itself[j_index] = range_query_answer;
}
if (2 == j_type) {
rectangle_R = &(rectangles_array_itself[j_index]);
range_query_answer = binary_indexed_tree__range_query(binary_indexed_tree_itself, rectangle_R->rectangle_y1, rectangle_R->rectangle_y2);
answers_array_itself[j_index] = range_query_answer - answers_array_itself[j_index];
}
if (1 == j_type) {
point_P = &(points_array_itself[j_index]);
binary_indexed_tree__point_update(binary_indexed_tree_itself, binary_indexed_tree_its_size, point_P->point_y);
}
if (j_type < 3) {
vertical_sweep_line_event_index += 1;
}
else {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INCORRECT_PROGRAM;
}
}
}
}
/* Step is pass the baton. */ {
return exit_status;
}
}
int zoo_program__write_all_the_answers_into_the_output_file_in_the_order_rectangle_questions_are_in_the_input_file (struct zoo_program__program_state * program_state_itself) {
/* Step is define and O(1) initialize O(1) variables local into the immediately enclosing lexical block scope. */ {
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is print the answers, the lot of them, in the correct order, first question answered first, second question answered second, and so on and so forth. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * const output_file_itself = program_state_itself->output_file_itself;
size_t const number_of_rectangles_itself = program_state_itself->number_of_rectangles_itself;
uint32_t ( * const answers_array_itself ) = program_state_itself->answers_array_itself;
size_t rectangle_index = 0;
int s_code = 0;
rectangle_index = 0;
while ((ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (rectangle_index < number_of_rectangles_itself)) {
s_code = fprintf(output_file_itself, "%" PRIu32 "\n", answers_array_itself[rectangle_index]);
if (0 >= s_code) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUTPUT_FILE;
}
else {
rectangle_index += 1;
}
}
}
}
/* Step is pass the baton. */ {
return exit_status;
}
}
int zoo_program__release_all_the_resources_down_back (struct zoo_program__program_state * program_state_itself, int exit_status) {
/* Step is release the output file itself. */ {
int const s_code = fclose(program_state_itself->output_file_itself);
program_state_itself->output_file_itself = NULL;
if (0 != s_code) {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__OUTPUT_FILE;
}
else {
perror("closing the output file");
}
}
}
/* Step is release the answers array itself. */ {
free(program_state_itself->answers_array_itself);
program_state_itself->answers_array_itself = NULL;
}
/* Step is clear the binary indexed tree its size. */ {
program_state_itself->binary_indexed_tree_its_size = 0;
}
/* Step is release the binary indexed tree itself. */ {
free(program_state_itself->binary_indexed_tree_itself);
program_state_itself->binary_indexed_tree_itself = NULL;
}
/* Step is clear the merge sort recursion stack its size. */ {
program_state_itself->merge_sort_recursion_stack_its_size = 0;
}
/* Step is release the merge sort recursion stack itself. */ {
free(program_state_itself->merge_sort_recursion_stack_itself);
program_state_itself->merge_sort_recursion_stack_itself = NULL;
}
/* Step is release the merge_sort_auxiliary_array_itself. */ {
free(program_state_itself->merge_sort_auxiliary_array_itself);
program_state_itself->merge_sort_auxiliary_array_itself = NULL;
}
/* Step is release the merge sort elements array itself. */ {
free(program_state_itself->merge_sort_elements_array_itself);
program_state_itself->merge_sort_elements_array_itself = NULL;
}
/* Step is clear the merge sort arrays_ ommon size itself. */ {
program_state_itself->merge_sort_arrays_common_size_itself = 0;
}
/* Step is release the rectangles array itself. */ {
free(program_state_itself->rectangles_array_itself);
program_state_itself->rectangles_array_itself = NULL;
}
/* Step is release the points array itself. */ {
free(program_state_itself->points_array_itself);
program_state_itself->points_array_itself = NULL;
}
/* Step is clear the number of rectangles itself. */ {
program_state_itself->number_of_rectangles_itself = 0;
}
/* Step is clear the number of points itself. */ {
program_state_itself->number_of_points_itself = 0;
}
/* Step is clear the line buffer itself. */ {
free(program_state_itself->line_buffer_itself);
program_state_itself->line_buffer_itself = NULL;
program_state_itself->line_buffer_its_capacity = 0;
}
/* Step is release the input file itself. */ {
int const c_code = fclose(program_state_itself->input_file_itself);
program_state_itself->input_file_itself = NULL;
if (0 != c_code) {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = ZOO_PROGRAM__EXIT_STATUS__NAY_FAILURE__INPUT_FILE;
}
else {
perror("input file");
}
}
}
/* Step is release the [storage hosting the] program state object itself. */ {
free(program_state_itself);
program_state_itself = NULL;
}
/* Step is pass the baton, to the caller routine. */ {
return exit_status;
}
}
int main (void) {
/* Step is define and O(1) initialize a handful of variables local into the immediately enclosing lexical block scope. */ {
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__OPEN
int exit_status = ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
struct zoo_program__program_state * program_state_itself = NULL;
ZOO_PROGRAM__FOLDING__INVERTED_BLOCK_SCOPE_CURLY_BRACKETS__CLOSE
}
/* Step is allocate all the resources up front, reading the problem from the input file; these two are cobbled together by the data format itself. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
struct zoo_program__program_state * pointer_p = NULL;
int const exit_status_too = zoo_program__allocate_all_the_required_resources_up_front_reading_the_problem_from_the_input_file(&pointer_p);
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
else {
program_state_itself = pointer_p;
}
}
}
/* Step is replace each Y coordiante with its position in the sorted array of the Y coordinate values, not counting duplicates. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int const exit_status_too = zoo_program__perform_one_change_of_variables_for_vertical_coordinates(program_state_itself);
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
}
/* Step is sort the vertical sweep line records preparing for point updates and range queries. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int const exit_status_too = zoo_program__sort_the_vertical_sweep_line_records_preparing_for_point_updates_and_range_queries (program_state_itself);
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
}
/* Step is move the vertical sweep line from left to right, solving all the queries, finding all the answers. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int const exit_status_too = zoo_program__move_the_vertical_sweep_line_left_to_right_solving_all_the_queries_finding_all_the_answers (program_state_itself);
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
}
/* Step is write all the answers into the output file, in the order the rectangle questions are in the input file. */ {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int const exit_status_too = zoo_program__write_all_the_answers_into_the_output_file_in_the_order_rectangle_questions_are_in_the_input_file (program_state_itself);
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
}
/* Step is release all the resources down back, everithing having been done, nothing remaining to do, except for passing the baton. */ {
if (NULL != program_state_itself) {
int const exit_status_too = zoo_program__release_all_the_resources_down_back(program_state_itself, exit_status);
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
if (ZOO_PROGRAM__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = exit_status_too;
}
}
}
}
/* Step is pass the baton, to the operating system, or more precisely the process wait () -ing our exit status code, maybe even wait4 () -ing. */ {
return exit_status;
}
}
#endif
Marius B mgnt