Overview

Given multiple rectangular advertisements from Takahashi and multiple rectangular advertisements from Aoki placed on an \(N \times N\) grid, the problem asks to find the number of cells that are covered by at least one advertisement from each of them.

Analysis

The answer can be obtained by checking, for each cell, whether it is covered by at least one of Takahashi’s advertisements and at least one of Aoki’s advertisements. However, naively computing the overlap for every pair of advertisements would require calculating up to \(A \times B = 10000\) combinations, and counting the number of cells in each overlapping region would be time-consuming. Moreover, since the same cell could be counted multiple times across different combinations, we would also need to eliminate duplicates.

To compute this efficiently, we use 2D prefix sums to separately calculate, for each cell, how many of Takahashi’s advertisements cover it and how many of Aoki’s advertisements cover it. This allows us to check the coverage status of both Takahashi’s and Aoki’s advertisements for each cell in \(O(1)\).

Algorithm

1. Using the 2D imos method, separately compute the number of covering advertisements from Takahashi’s group and Aoki’s group for each cell.
   • For each advertisement, add +1 at the top-left \((r1, c1)\), -1 at the top-right \((r1, c2+1)\), -1 at the bottom-left \((r2+1, c1)\), and +1 at the bottom-right \((r2+1, c2+1)\).
2. Then, by taking the 2D prefix sum, compute the coverage count for each cell \((i, j)\).
   • \(board[i][j] = board[i][j] + board[i-1][j] + board[i][j-1] - board[i-1][j-1]\)
3. Finally, for each cell, check whether Takahashi’s coverage count is at least 1 and Aoki’s coverage count is at least 1, and count the number of cells satisfying the condition.

Complexity

• Time complexity: \(O(N^2 + A + B)\)
  • Addition processing for the imos method: \(O(A + B)\)
  • Prefix sum computation: \(O(N^2)\)
  • Checking cells: \(O(N^2)\)
• Space complexity: \(O(N^2)\)

Implementation Notes

• Since the grid size is \(N \leq 500\), allocating a \(500 \times 500\) 2D array is sufficient. However, to prevent out-of-bounds access when computing prefix sums, the array is allocated with size \((N+2) \times (N+2)\).

• In the imos method, since we add values at the cell next to the bottom-right of the advertisement, care must be taken with indices (\(r2+1\), \(c2+1\)).

• When computing the prefix sum, using 1-indexed loops makes the implementation straightforward.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); A = int(data[idx+1]); B = int(data[idx+2]); idx += 3
    
    board_t = [[0] * (N+2) for _ in range(N+2)]
    board_a = [[0] * (N+2) for _ in range(N+2)]
    
    for i in range(A):
        r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); idx += 4
        board_t[r1][c1] += 1
        board_t[r1][c2+1] -= 1
        board_t[r2+1][c1] -= 1
        board_t[r2+1][c2+1] += 1
        
    for j in range(B):
        r1 = int(data[idx]); c1 = int(data[idx+1]); r2 = int(data[idx+2]); c2 = int(data[idx+3]); idx += 4
        board_a[r1][c1] += 1
        board_a[r1][c2+1] -= 1
        board_a[r2+1][c1] -= 1
        board_a[r2+1][c2+1] += 1
        
    for i in range(1, N+1):
        for j in range(1, N+1):
            board_t[i][j] += board_t[i-1][j] + board_t[i][j-1] - board_t[i-1][j-1]
            board_a[i][j] += board_a[i-1][j] + board_a[i][j-1] - board_a[i-1][j-1]
            
    count = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            if board_t[i][j] > 0 and board_a[i][j] > 0:
                count += 1
                
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.