2024-ho-t4_Gift_Exchange — JOI JOI
Task type: batch | Time limit: 2.5 s | Memory limit: 1024 MB | Difficulty: 23
Algorithms: divide and conquer, hall's theorem, data structures, segment tree, offline queries

![](_page_0_Picture_0.jpeg)

# Gift Exchange

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, and the value of the gift that student $i$ ($1 \le i \le N$) will bring is $A_i$. Students are unwilling to receive a gift whose value is 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, the $j$-th ($1 \le j \le 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 \ge 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 \le k \le m$) represents the student who gives their gift to student $p_k$.

*   For all $k$ ($1 \le k \le m$), $p_k \ne q_k$.
*   For all $k$ ($1 \le k \le m$), $A_{q_k} \ge B_{p_k}$.

President K is keen to make the gift exchange party successful and is 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.

## Input

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

```
N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q
```

## Output

Write $Q$ lines to Standard Output. On the $j$-th line ($1 \le j \le Q$), output `Yes` if the $j$-th group is gift exchangeable, and `No` otherwise.

## Constraints

*   $2 \le N \le 500\,000$
*   $1 \le B_i < A_i \le 2N$ ($1 \le i \le N$)
*   $A_1, B_1, A_2, B_2, \dots, A_N, B_N$ are all distinct.
*   $1 \le Q \le 200\,000$
*   $1 \le L_j < R_j \le N$ ($1 \le j \le Q$)
*   All values in the input are integers.

![](_page_2_Picture_0.jpeg)

## Subtasks

1.  (4 points) $N \le 10$, $Q \le 10$
2.  (5 points) $N \le 18$, $Q \le 10$
3.  (10 points) $N \le 100\,000$, $A_1 \ge 2N - 2$, $B_1 = 1$, $Q = 1$, $L_1 = 1$, $R_1 = N$
4.  (31 points) $N \le 100\,000$, $Q \le 10$
5.  (8 points) $N \le 100\,000$, $A_i < A_{i+1}$, $B_i < B_{i+1}$ ($1 \le i \le N - 1$)
6.  (12 points) $N \le 100\,000$, $A_i < A_{i+1}$ ($1 \le i \le N - 1$)
7.  (18 points) $N \le 100\,000$
8.  (12 points) No additional constraints

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 4              | Yes            |
| 3 8 5 7        | No             |
| 2 6 1 4        | Yes            |
| 3              |                |
| 3 4            |                |
| 1 3            |                |
| 1 4            |                |

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 \ge B_4$ and $A_4 \ge B_3$. Therefore, this group is gift exchangeable, and the output is `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 the output is `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 gift, student 2 receives student 4's gift, student 3 receives student 1's gift, and student 4 receives student 3's gift, none of the students will be dissatisfied. Therefore, this group is gift exchangeable, and the output is `Yes` on the third line.

This sample input satisfies the constraints of Subtasks 1, 2, 4, 7, 8.

![](_page_3_Picture_0.jpeg)

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 3              | Yes            |
| 5 6 3          |                |
| 1 4 2          |                |
| 1              |                |
| 1 3            |                |

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 7, 8.

| Sample Input 3 | Sample Output 3 |
| :------------- | :------------- |
| 5              | No             |
| 3 4 6 9 10     | Yes            |
| 1 2 5 7 8      | No             |
| 3              |                |
| 1 5            |                |
| 1 2            |                |
| 2 4            |                |

This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6, 7, 8.

| Sample Input 4             | Sample Output 4 |
| :------------------------- | :------------- |
| 10                         | No             |
| 2 5 8 10 12 14 16 17 19 20 | No             |
| 1 4 7 6 11 13 9 3 18 15    | Yes            |
| 8                          | No             |
| 2 9                        | No             |
| 1 6                        | No             |
| 2 8                        | Yes            |
| 2 4                        | Yes            |
| 1 2                        |                |
| 1 6                        |                |
| 7 10                       |                |
| 5 8                        |                |

This sample input satisfies the constraints of Subtasks 1, 2, 4, 6, 7, 8.

Starter code: