D - Clouds Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

空は 2000 \times 2000 のマス目で表されます。
空を見上げた時、上から r 行目、左から c 列目にあるマスを (r,c) と呼びます。

いま、この空には雲 1,2,\dots,N が浮かんでいます。
整数の組 (r,c) が U_i \le r \le D_i, L_i \le c \le R_i を満たすとき、またその時に限り、 (r,c) は雲 i で覆われています。

k=1,2,\dots,N について、以下の問いに答えてください。

  • N 個の雲のうち、雲 k のみを取り除く。この時点で空には N-1 個の雲が浮かんでいる。このとき、どの雲にも覆われていないマスがいくつあるか答えよ。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le U_i \le D_i \le 2000
  • 1 \le L_i \le R_i \le 2000
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
U_1 D_1 L_1 R_1
U_2 D_2 L_2 R_2
\vdots
U_N D_N L_N R_N

出力

N 行出力せよ。
i 行目には、 k=i とした場合の問いの答えを出力せよ。

入力例 1

5
2 4 1 4
3 3 3 5
1 3 4 6
4 5 3 5
5 5 4 6

出力例 1

3999983
3999976
3999982
3999978
3999977

図は、空のうち左上 5 \times 6 の領域を抜き出したものです。

  • 雲 1 を取り除いた際、何らかの雲に覆われているマスは 17 マスなので、どの雲にも覆われていないマスは 3999983 マスです。
  • 雲 2 を取り除いた際、何らかの雲に覆われているマスは 24 マスなので、どの雲にも覆われていないマスは 3999976 マスです。
  • 雲 3 を取り除いた際、何らかの雲に覆われているマスは 18 マスなので、どの雲にも覆われていないマスは 3999982 マスです。
  • 雲 4 を取り除いた際、何らかの雲に覆われているマスは 22 マスなので、どの雲にも覆われていないマスは 3999978 マスです。
  • 雲 5 を取り除いた際、何らかの雲に覆われているマスは 23 マスなので、どの雲にも覆われていないマスは 3999977 マスです。

Score : 425 points

Problem Statement

The sky is represented by a 2000 \times 2000 grid.
When looking up at the sky, the cell at the r-th row from the top and c-th column from the left is called (r,c).

Currently, there are clouds 1,2,\dots,N floating in this sky.
The cell (r,c) is covered by cloud i if and only if it satisfies U_i \le r \le D_i and L_i \le c \le R_i.

For k=1,2,\dots,N, answer the following question:

  • Remove only cloud k from the N clouds. At this point, there are N-1 clouds floating in the sky. How many cells are not covered by any cloud?

Constraints

  • 1 \le N \le 2 \times 10^5
  • 1 \le U_i \le D_i \le 2000
  • 1 \le L_i \le R_i \le 2000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
U_1 D_1 L_1 R_1
U_2 D_2 L_2 R_2
\vdots
U_N D_N L_N R_N

Output

Output N lines.
The i-th line should contain the answer to the question when k=i.

Sample Input 1

5
2 4 1 4
3 3 3 5
1 3 4 6
4 5 3 5
5 5 4 6

Sample Output 1

3999983
3999976
3999982
3999978
3999977

The figure shows the top-left 5 \times 6 region of the sky.

  • When cloud 1 is removed, the number of cells covered by some cloud is 17, so the number of cells not covered by any cloud is 3999983.
  • When cloud 2 is removed, the number of cells covered by some cloud is 24, so the number of cells not covered by any cloud is 3999976.
  • When cloud 3 is removed, the number of cells covered by some cloud is 18, so the number of cells not covered by any cloud is 3999982.
  • When cloud 4 is removed, the number of cells covered by some cloud is 22, so the number of cells not covered by any cloud is 3999978.
  • When cloud 5 is removed, the number of cells covered by some cloud is 23, so the number of cells not covered by any cloud is 3999977.