| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 118 | 36 | 30 | 28.846% |
JOI Academy has $N$ students, numbered from 1ドル$ to $N$.
A gift exchange party is planned to be held soon at JOI Academy. Each student has prepared a gift to bring there, and the value of the gift that student $i$ (1ドル ≤ i ≤ N$) will bring is $A_i$. Students are unwilling to receive a gift whose value is too less than that of their own gift. Specifically, student $i$ will be dissatisfied if they receive a gift with a value strictly less than $B_i$. Here, $B_i < A_i$ always holds.
However, some of the $N$ students may not actually participate in the party. President $K,ドル the director of JOI Academy, is considering $Q$ possible groups of students as a group to participate in the gift exchange party, $j$-th (1ドル ≤ j ≤ Q$) of which consists of $R_j - L_j + 1$ students $L_j , L_j + 1,\dots , R_j$.
For some group of two or more students, if it is possible to exchange gifts within the group without anyone receiving their own gift or getting dissatisfied, that group is said to be gift exchangeable. More formally, a group of $m$ students ($m ≥ 2$) $p_1, p_2, \dots , p_m$ is gift exchangeable if and only if there exists a sequence $q_1, q_2, \dots , q_m$ which is a permutation of $p_1, p_2, \dots , p_m$ and satisfies each of the following conditions. Here, $q_k$ (1ドル ≤ k ≤ m$) represents the number of student who gives their gift to student $p_k$.
President K is keen to make the gift exchange party successful, and thus examining whether each of the $Q$ groups is gift exchangeable or not.
Write a program which, given information of students and groups, determines whether each of the $Q$ groups is gift exchangeable or not.
Read the following data from the standard input.
$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$
Write $Q$ lines to the standard output. On the $j$-th line (1ドル ≤ j ≤ Q$), output Yes if the $j$-th group is gift exchangeable, and No otherwise.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $N ≤ 10,ドル $Q ≤ 10$. |
| 2 | 5 | $N ≤ 18,ドル $Q ≤ 10$. |
| 3 | 10 | $N ≤ 100,円 000,ドル $A_1 ≥ 2N - 2,ドル $B_1 = 1,ドル $Q = 1,ドル $L_1 = 1,ドル $R_1 = N$. |
| 4 | 31 | $N ≤ 100,円 000,ドル $Q ≤ 10$. |
| 5 | 8 | $N ≤ 100,円 000,ドル $A_i < A_{i+1},ドル $B_i < B_{i+1}$ (1ドル ≤ i ≤ N - 1$). |
| 6 | 12 | $N ≤ 100,円 000,ドル $A_i < A_{i+1}$ (1ドル ≤ i ≤ N - 1$). |
| 7 | 18 | $N ≤ 100,円 000$. |
| 8 | 12 | No additional constraints. |
4 3 8 5 7 2 6 1 4 3 3 4 1 3 1 4
Yes No Yes
The first group consists of 2ドル$ students 3ドル,ドル 4ドル$. If student 3ドル$ receives student 4ドル$’s gift, and student 4ドル$ receives student 3ドル$’s gift, neither of the students will be dissatisfied as $A_3 ≥ B_4$ and $A_4 ≥ B_3$. Therefore, this group is gift exchangeable, and output Yes on the first line.
The second group consists of 3ドル$ students 1ドル,ドル 2ドル,ドル 3ドル$. Since $A_1 < B_2$ and $A_3 < B_2,ドル student 2ドル$ will be dissatisfied whichever gift of student 1ドル$ or 3ドル$ they receive. Therefore, this group is not gift exchangeable, and output No on the second line.
The third group consists of 4ドル$ students 1ドル,ドル 2ドル,ドル 3ドル,ドル 4ドル$. For instance, if student 1ドル$ receives student 2ドル$’s, student 2ドル$ receives student 4ドル$’s, student 3ドル$ receives student 1ドル$’s, and student 4ドル$ receives student 3ドル$’s gift, none of the students will be dissatisfied. Therefore, this group is gift exchangeable, and output Yes on the third line.
This sample input satisfies the constraints of Subtasks 1, 2, 4, 7, 8.
3 5 6 3 1 4 2 1 1 3
Yes
This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 7, 8.
5 3 4 6 9 10 1 2 5 7 8 3 1 5 1 2 2 4
No Yes No
This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6, 7, 8.
10 2 5 8 10 12 14 16 17 19 20 1 4 7 6 11 13 9 3 18 15 8 2 9 1 6 2 8 2 4 1 2 1 6 7 10 5 8
No No Yes No No No Yes Yes
This sample input satisfies the constraints of Subtasks 1, 2, 4, 6, 7, 8.