問題一覧 > 通常問題

No.961 Vibrant Fillumination

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 13
作問者 : kopricky / テスター : Pachicobue
お気に入りにしたユーザー ProblemId : 2539 / 自分の提出
問題文最終更新日: 2020-02-01 19:51:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

Problem Statement

Hoge-chan bought $N$ colored rectangular films and placed all of them on a glass plate.
Viewing the glass plate as the $xy$-plane, each rectangle is placed so that each of its sides is parallel to the $x$-axis or the $y$-axis.
The position of the $i$-th rectangle is represented by the coordinates $(a_i, b_i)$ of its lower-left corner and the coordinates $(c_i, d_i)$ of its upper-right corner, and its color is $e_i$.
Films may overlap one another.
Since the films are translucent, shining a light from beneath the glass plate makes the color of a film stand out vividly.
Where films of different colors overlap, a new color different from either of the 2 colors appears.
Specifically, the color at coordinates $(x, y)$ is represented as the set without duplicates of the colors of all films that contain $(x, y)$ in their interior (see the sample for details).
Hoge-chan was about to shine the light and make the colors appear, but unfortunately the light's battery has run out, so no light can be shone, and Hoge-chan is sad.
So you have decided to write, for Hoge-chan, a program that answers queries asking what color $(p + 0.5, q + 0.5)$ would be when lit from below.
Let $S = \{ k_1, k_2, \ldots, k_l \}$ be the set without duplicates representing the color of $(p + 0.5, q + 0.5)$. Answering with this set directly could make the output very large.
Therefore, in this problem, return as the answer the value $h_{k_1}$ $\oplus$ $h_{k_2}$ $\cdots$ $\oplus$ $h_{k_l}$, computed using the hash value $h_i$ assigned to each color.
Here, $\oplus$ denotes the exclusive OR (xor) operation. When $S = \emptyset$, return $0$.

Input

$N$
$h_1$ $h_2$ $\ldots$ $h_N$
$a_1$ $b_1$ $c_1$ $d_1$ $e_1$
$\vdots$
$a_N$ $b_N$ $c_N$ $d_N$ $e_N$
$Q$
$p_1$ $q_1$
$\vdots$
$p_Q$ $q_Q$

The first line contains the number of films $N$.
The second line represents the hash values assigned to the colors; the hash value of color $i$ is $h_i$.
The following $N$ lines, starting from line 3, give the coordinates $(a_i, b_i)$ of the lower-left corner, the coordinates $(c_i, d_i)$ of the upper-right corner, and the color $e_i$ of the $i$-th film.
Line $N + 3$ contains the number of queries $Q$.
The following $Q$ lines, starting from line $N + 4$, give the coordinates $(p_i, q_i)$ for the $i$-th query.
Constraints
$1 \le N \le 5 \times 10^4$
$0 \le h_i < 2^{60}$
$0 \le a_i, b_i, c_i, d_i < 2N$
$a_i < c_i$
$b_i < d_i$
$1 \le e_i \le N$
$1 \le Q \le 5 \times 10^4$
$0 \le p_i, q_i < 2N$
All inputs are integers.

Output

Output $Q$ lines. On the $i$-th line, return as the answer to the $i$-th query the value $h_{k_1}$ $\oplus$ $h_{k_2}$ $\cdots$ $\oplus$ $h_{k_l}$ corresponding to the color of $(p_i + 0.5, q_i + 0.5)$.
Print a newline at the end.

Sample

Sample 1
Input
 
4
1 2 4 8
3 0 6 5 1
1 3 4 6 2
2 4 5 7 3
0 1 7 2 1
9
1 4
3 4
4 1
6 3
0 1
4 4
2 5
3 3
4 6
Output
2
7
1
0
1
5
6
3
4


For example, at the position of the query $i = 2$, films of colors $1$, $2$, $3$ overlap, so the hash value is $h_1 \oplus h_2 \oplus h_3 = 7$.
At the position of the query $i = 3$, $2$ red (color $1$) films overlap, but since the color at each coordinate is represented as a set "without duplicates", it is the same as the color at the position of the query $i = 5$.
At the position of the query $i = 4$, no film contains that coordinate in its interior, so the corresponding hash value is $0$.

Sample 2
Input
6
1122712982464266027 690571985097146340 492323680811811014 422387876601185524 157370045133254199 705415601332626468
0 0 1 1 1
0 0 2 2 2
0 0 3 3 3
2 2 5 5 4
3 3 5 5 5
4 4 5 5 6
5
2 4
4 4
2 2
0 0
1 0
Output
422387876601185524
1025038893234884327
218858125916357682
59918757534908425
1099003965774774050

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。