Overview

On an \(N \times N\) bulletin board, we need to find the number of cells covered by both Takahashi’s advertisements (multiple rectangles) and Aoki’s advertisements (multiple rectangles). We use 2D imos method (2D prefix sum difference) to efficiently compute the coverage state of each cell.

Analysis

Naive Approach and Its Issues

The simplest method would be to consider all pairs of Takahashi’s and Aoki’s advertisements (up to \(A \times B = 10000\) pairs), compute the overlapping rectangle for each pair, and manage covered cells using a set. However, each rectangle can cover up to \(N^2 = 250000\) cells, making the overall computation potentially very large.

Key Insight

In this problem, it suffices to determine for each cell whether “it is covered by at least one of Takahashi’s advertisements” and whether “it is covered by at least one of Aoki’s advertisements.” Specifically, for each cell:

• Covered by one or more of Takahashi’s advertisements → flag ON
• Covered by one or more of Aoki’s advertisements → flag ON
• Count cells where both flags are ON

The operation of “adding a value to a rectangular region in bulk and then computing the cumulative value at each cell” can be efficiently performed using the 2D imos method.

Algorithm

How the 2D Imos Method Works

When we want to add \(+1\) to the rectangle from \((r_1, c_1)\) to \((r_2, c_2)\), we update the following 4 points in an \((N+2) \times (N+2)\) array:

• \(grid[r_1][c_1] += 1\)
• \(grid[r_1][c_2+1] -= 1\)
• \(grid[r_2+1][c_1] -= 1\)
• \(grid[r_2+1][c_2+1] += 1\)

After performing this operation for all rectangles, we take prefix sums in both the row and column directions, and the value at each cell \((r, c)\) becomes the number of rectangles covering that cell.

\[grid[r][c] += grid[r-1][c] + grid[r][c-1] - grid[r-1][c-1]\]

Procedure

1. For Takahashi’s \(A\) advertisements, apply the 2D imos method additions to array grid_a
2. For Aoki’s \(B\) advertisements, apply the 2D imos method additions to array grid_b
3. Compute prefix sums for both arrays
4. For each cell \((r, c)\), if \(grid\_a[r][c] > 0\) and \(grid\_b[r][c] > 0\), count it as an overlap

Concrete Example

For example, with \(N=5\), if Takahashi’s advertisement covers \((1,1)\) to \((3,3)\) and Aoki’s advertisement covers \((2,2)\) to \((4,4)\), then after computing prefix sums, the cells where \(grid\_a[r][c] > 0\) and \(grid\_b[r][c] > 0\) are \((2,2)\) to \((3,3)\), which is \(4\) cells.

Complexity

• Time complexity: \(O(N^2 + A + B)\)
  • The difference updates for the imos method take \(O(A + B)\), and the prefix sum computation and counting take \(O(N^2)\)
• Space complexity: \(O(N^2)\)
  • Two \((N+2) \times (N+2)\) arrays are used

Implementation Notes

• By setting the array size to \((N+2) \times (N+2)\), we prevent out-of-bounds access even when \(r_2+1\) or \(c_2+1\) equals \(N+1\)

• When computing prefix sums, don’t forget to subtract \(grid[r-1][c-1]\) (inclusion-exclusion principle)

• The check \(grid\_a[r][c] > 0\) confirms “whether the cell is covered by at least one advertisement.” It doesn’t matter if multiple advertisements overlap — only whether the cell is covered or not is important

• Using sys.stdin.read() to read all input at once allows fast execution even in Python

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    A = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1

    # 2D imos for Takahashi
    grid_a = [[0] * (N + 2) for _ in range(N + 2)]
    for _ in range(A):
        r1 = int(input_data[idx]); idx += 1
        c1 = int(input_data[idx]); idx += 1
        r2 = int(input_data[idx]); idx += 1
        c2 = int(input_data[idx]); idx += 1
        grid_a[r1][c1] += 1
        grid_a[r1][c2 + 1] -= 1
        grid_a[r2 + 1][c1] -= 1
        grid_a[r2 + 1][c2 + 1] += 1

    # 2D imos for Aoki
    grid_b = [[0] * (N + 2) for _ in range(N + 2)]
    for _ in range(B):
        r1 = int(input_data[idx]); idx += 1
        c1 = int(input_data[idx]); idx += 1
        r2 = int(input_data[idx]); idx += 1
        c2 = int(input_data[idx]); idx += 1
        grid_b[r1][c1] += 1
        grid_b[r1][c2 + 1] -= 1
        grid_b[r2 + 1][c1] -= 1
        grid_b[r2 + 1][c2 + 1] += 1

    # Compute prefix sums and count overlaps
    count = 0
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            grid_a[r][c] += grid_a[r - 1][c] + grid_a[r][c - 1] - grid_a[r - 1][c - 1]
            grid_b[r][c] += grid_b[r - 1][c] + grid_b[r][c - 1] - grid_b[r - 1][c - 1]
            if grid_a[r][c] > 0 and grid_b[r][c] > 0:
                count += 1

    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.