Overview

Find the set of cells covered by Takahashi’s advertisements and the set of cells covered by Aoki’s advertisements, then count the number of cells that are contained in both sets (i.e., overlapping cells).

Analysis

Since each advertisement is a rectangle, naively “painting every cell inside the rectangle one by one” for each advertisement would, in the worst case, process an area close to \(N^2\) a total of \(A+B\) times, which tends to be too slow in Python (up to approximately \(200 \times 500 \times 500 = 50,000,000\) cell updates).

Alternatively, if we try to check overlaps as “each of Takahashi’s rectangles × each of Aoki’s rectangles,” while we can compute the intersection of two rectangles, handling “not counting the same cell multiple times” becomes cumbersome.

The key insight is as follows:

• What we need is only whether each cell is “covered at least once by Takahashi” and “covered at least once by Aoki” (the exact count is unnecessary; we only need to check whether it is \(>0\)).
• Bulk addition over a rectangle can be done efficiently using a 2D difference array (2D imos method).

With this approach, each rectangle is reflected in the difference array in \(O(1)\), and finally in \(O(N^2)\) we can reconstruct the coverage count for all cells and count the overlaps.

Algorithm

We independently apply the 2D imos method for Takahashi and for Aoki.

1. Updating the 2D Difference Array (Imos Method)

Let cell \((r, c)\) be 1-indexed. To “paint with +1” the rectangle from \((r_1,c_1)\) to \((r_2,c_2)\), add the following to the difference array diff:

• diff[r1][c1] += 1
• diff[r1][c2+1] -= 1
• diff[r2+1][c1] -= 1
• diff[r2+1][c2+1] += 1

By doing this, when we later take the 2D prefix sum, only the rectangular region will be incremented by +1. To safely handle the boundary values r2+1 and c2+1, the array size is set to \((N+2)\times(N+2)\).

2. Restoring Coverage Counts with Prefix Sums

To obtain the actual coverage count cover from diff, we take a 2D prefix sum. In the implementation:

1. Accumulate in the row direction (sum horizontally)
2. Accumulate in the column direction (sum from top to bottom)

Processing in this order gives us “how many times each cell is covered by that person’s advertisements.”

3. Counting Overlapping Cells

For every cell \((r,c)\), if both of the following conditions are satisfied:

• Takahashi’s coverage count coverA[r][c] > 0
• Aoki’s coverage count coverB[r][c] > 0

then that cell is overlapping, so we add +1 to the answer. Even if the same cell is covered by multiple advertisements, the condition is only whether the count is \(>0\), so it is naturally “counted only once.”

Complexity

• Time complexity: \(O((A+B) + N^2)\) (Difference array updates for rectangles are \(O(A+B)\), and prefix sums plus aggregation are \(O(N^2)\))
• Space complexity: \(O(N^2)\) (Arrays are maintained for both Takahashi and Aoki)

Implementation Notes

• Allocate arrays of size \((N+2)\times(N+2)\) so that updates to r2+1 and c2+1 can be written without boundary checks.

• Restoring from the imos method (prefix sums) can be done in two stages: “horizontal → vertical.”

• At the end, a \(> 0\) check is sufficient (it directly expresses the condition “covered by at least one advertisement”).

  Source Code

import sys
from array import array

def build_cover(diff, n):
    # horizontal prefix
    for r in range(1, n + 1):
        row = diff[r]
        s = 0
        for c in range(1, n + 1):
            s += row[c]
            row[c] = s
    # vertical prefix
    for r in range(1, n + 1):
        row = diff[r]
        prev = diff[r - 1]
        for c in range(1, n + 1):
            row[c] += prev[c]

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    A = next(it)
    B = next(it)

    W = N + 2
    diffA = [array('i', [0]) * W for _ in range(W)]
    diffB = [array('i', [0]) * W for _ in range(W)]

    for _ in range(A):
        r1 = next(it); c1 = next(it); r2 = next(it); c2 = next(it)
        diffA[r1][c1] += 1
        diffA[r1][c2 + 1] -= 1
        diffA[r2 + 1][c1] -= 1
        diffA[r2 + 1][c2 + 1] += 1

    for _ in range(B):
        r1 = next(it); c1 = next(it); r2 = next(it); c2 = next(it)
        diffB[r1][c1] += 1
        diffB[r1][c2 + 1] -= 1
        diffB[r2 + 1][c1] -= 1
        diffB[r2 + 1][c2 + 1] += 1

    build_cover(diffA, N)
    build_cover(diffB, N)

    ans = 0
    for r in range(1, N + 1):
        rowA = diffA[r]
        rowB = diffB[r]
        for c in range(1, N + 1):
            if rowA[c] > 0 and rowB[c] > 0:
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.