No.961 Vibrant Fillumination
タグ : / 解いたユーザー数 13
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。