Consider a rectangular coordinate grid with dimensions N rows by M columns. This grid is uniformly partitioned into rectangular blocks, each measuring R rows by C columns. The partitioning guarantees that N is a multiple of R and M is a multiple of C.

Given a query rectangle defined by its top-left coordinate (X₁, Y₁) and bottom-right coordinate (X₂, Y₂), the objective is to determine the total count of distinct blocks that are either intersected by or fully contained within the query boundaries.

Mathematical Derivation

Because the block partitioning is uniform and axis-aligned, the problem decouples into two independent one-dimensional calculations. For any coordinate axis, consecutive indices belong to the same block index as long as their integer division by the block size yields the same quotient.

Along the vertical axis, the block index for a row i is ⌊i / R⌋. The number of unique block indices intersected by the range [X₁, X₂] corresponds to the number of distinct quotients generated within that interval. This can be computed directly using the endpoints:

vertical_span = ⌊X₂ / R⌋ - ⌊X₁ / R⌋ + 1

Similarly, the horizontal span is determined by dividing column coordinates by C:

horizontal_span = ⌊Y₂ / C⌋ - ⌊Y₁ / C⌋ + 1

The total number of intersected blocks is the Cartesian product of these two spans. This formulation eliminates the need for iterative boundary checks, reducing the computational complexity to constant time.

Optimized Implementation

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long total_rows, total_cols, block_rows, block_cols;
    if (!(cin >> total_rows >> total_cols >> block_rows >> block_cols)) return 0;

    long long r_start, c_start, r_end, c_end;
    cin >> r_start >> c_start >> r_end >> c_end;

    // Determine unique vertical block indices intersected
    long long intersected_rows = (r_end / block_rows) - (r_start / block_rows) + 1;

    // Determine unique horizontal block indices intersected
    long long intersected_cols = (c_end / block_cols) - (c_start / block_cols) + 1;

    // Combine independent dimensions
    long long result = intersected_rows * intersected_cols;
    cout << result << "\n";

    return 0;
}

Performance Characteristics

Time Complexity: O(1). The solution relies exclusively on arithmetic operations and integer division, executing in constant time regardless of grid dimensions.

Space Complexity: O(1). Only a fixed set of scalar variables is allocated in memory.