Overview

On an \(N \times N\) bulletin board, Takahashi and Aoki each post multiple rectangular advertisements. We need to find the total number of cells where both of their advertisements overlap.

Analysis

In this problem, Takahashi and Aoki each have multiple advertisements, each covering a rectangular region. A naive approach would be to compute the overlap for every pair of advertisements, but this would require up to \(A \times B = 100 \times 100 = 10^4\) comparisons in the worst case, and each advertisement can be as large as \(N \times N = 500 \times 500 = 2.5 \times 10^5\) cells, causing the computational complexity to explode with a brute-force method.

Instead, we use a two-dimensional prefix sum (2D imos method) to efficiently record which cells each advertisement covers. Specifically, we add “+1” to the interval corresponding to each advertisement, and then take the prefix sum to quickly determine how many advertisements cover each cell.

Using this method, we separately compute the coverage count from Takahashi’s advertisements and from Aoki’s advertisements, and then count the cells where both counts are 1 or more to obtain the answer.

Algorithm

1. For all of Takahashi’s advertisements, use the 2D imos method to compute how many advertisements cover each cell.
2. Similarly, apply the 2D imos method for Aoki’s advertisements.
3. For each cell, if it is covered by at least one of Takahashi’s advertisements and at least one of Aoki’s advertisements, count that cell.
4. Output the final count of such cells.

Key Points of the 2D Imos Method:

• Since coordinates are 1-indexed, adjust indices during array operations (e.g., grid[r1-1][c1-1]).
• For range addition, perform sign-flipping operations at the four corners.
• Finally, take the prefix sum in the row direction then the column direction (or column then row) to finalize the count for each cell.

Complexity

• Time complexity: \(O(N^2 + A + B)\)
  • Range addition is performed in constant time for each advertisement, followed by taking the prefix sum twice over the \(N \times N\) grid.
• Space complexity: \(O(N^2)\)
  • Two-dimensional arrays are used to record Takahashi’s and Aoki’s advertisements.

Implementation Notes

• Be careful with coordinate conversion (1-indexed → 0-indexed).
• In the 2D imos method, if conditions are needed to properly handle interval boundaries and prevent out-of-bounds access.
• In the final scan, overlap is detected by checking whether the values in both grids are 1 or more.

## Source Code

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    A = int(data[idx]); idx += 1
    B = int(data[idx]); idx += 1
    
    # 高橋君の広告
    T = []
    for _ in range(A):
        r1 = int(data[idx]); idx += 1
        c1 = int(data[idx]); idx += 1
        r2 = int(data[idx]); idx += 1
        c2 = int(data[idx]); idx += 1
        T.append((r1, c1, r2, c2))
    
    # 青木君の広告
    Aoki = []
    for _ in range(B):
        r1 = int(data[idx]); idx += 1
        c1 = int(data[idx]); idx += 1
        r2 = int(data[idx]); idx += 1
        c2 = int(data[idx]); idx += 1
        Aoki.append((r1, c1, r2, c2))
    
    # 二次元累積和を使って高速化
    # 座標圧縮は不要（N<=1000で可能）
    # 各広告をビットマップ的に処理するより、区間加算＋最後に走査の方が良い
    
    # 高橋君の広告をすべて塗る（+1）
    grid = [[0] * (N+1) for _ in range(N+1)]
    
    for r1, c1, r2, c2 in T:
        grid[r1-1][c1-1] += 1
        if r2 < N:
            grid[r2][c1-1] -= 1
        if c2 < N:
            grid[r1-1][c2] -= 1
        if r2 < N and c2 < N:
            grid[r2][c2] += 1
    
    # 縦方向の累積和
    for i in range(N):
        for j in range(N):
            if i > 0:
                grid[i][j] += grid[i-1][j]
    
    # 横方向の累積和
    for i in range(N):
        for j in range(N):
            if j > 0:
                grid[i][j] += grid[i][j-1]
    
    # grid[i][j] now contains the number of Takahashi ads covering cell (i+1,j+1)
    
    # Now count how many cells are covered by at least one Takahashi ad AND at least one Aoki ad
    # We'll use another grid to mark Aoki coverage, then intersect
    
    aoki_grid = [[0] * (N+1) for _ in range(N+1)]
    
    for r1, c1, r2, c2 in Aoki:
        aoki_grid[r1-1][c1-1] += 1
        if r2 < N:
            aoki_grid[r2][c1-1] -= 1
        if c2 < N:
            aoki_grid[r1-1][c2] -= 1
        if r2 < N and c2 < N:
            aoki_grid[r2][c2] += 1
    
    # 縦方向の累積和
    for i in range(N):
        for j in range(N):
            if i > 0:
                aoki_grid[i][j] += aoki_grid[i-1][j]
    
    # 横方向の累積和
    for i in range(N):
        for j in range(N):
            if j > 0:
                aoki_grid[i][j] += aoki_grid[i][j-1]
    
    count = 0
    for i in range(N):
        for j in range(N):
            if grid[i][j] >= 1 and aoki_grid[i][j] >= 1:
                count += 1
                
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.