No.3705 Bibako and Macaron
Rapca1256
tomorunnNote
Note that the execution time limit per test case for this problem is 3.0sec.Problem Statement
The beavers Bitaro and Bibako bought a box containing $N$ macarons.
There are $N$ flavors of macarons, and the $i$-th macaron has flavor $A_i$. ($1 \le A_i \le N$)
You are given $Q$ independent queries; answer each of them. The $i$-th query is as follows.
- Bitaro wants to eat macarons of the flavors from $L_i$ to $R_i$, inclusive, and Bibako wants to eat macarons of the flavors from $L'_i$ to $R'_i$, inclusive, $1$ of each flavor.
Determine whether there is a way for them to choose and eat $R_i - L_i + 1$ and $R'_i - L'_i + 1$ macarons from the box, respectively, without overlap, such that each of them eats all the flavors they want to eat.
Input
$N$ $A_1\ A_2\ \cdots\ A_N$ $Q$ $L_1\ R_1\ L'_1\ R'_1$ $L_2\ R_2\ L'_2\ R'_2$ $\cdots$ $L_Q\ R_Q\ L'_Q\ R'_Q$
Constraints
- $1 \le N, Q \le 5\times 10^5$.
- $1 \le L_i \le R_i \le N$.
- $1 \le L'_i \le R'_i \le N$.
- All input values are integers.
Partial Score
This problem has partial scoring based on subtasks.
| Subtask | Score | Constraints |
|---|---|---|
| 小課題1 | 10% (20 pts) | $N \le 100, Q \le 100$, 各質問について, $L_i=R_i,L'_i=R'_i$. |
| 小課題2 | 30% (60 pts) | $N \le 100, Q \le 100$. |
| 小課題3 | 60% (120 pts) | 追加の制約はない. |
Output
Print $Q$ lines.
On the $i$-th line, print Yes if the answer to the $i$-th query is that it is possible, and No otherwise.
Do not print anything other than the answers. (Do not print text such as input prompts either.)
Sample
Sample 1
Input
6 1 3 2 2 1 4 3 2 4 1 2 1 4 2 3 1 5 1 1
Output
Yes No No
For query $1$, Bitaro can eat the macarons numbered $2, 3, 6$, and Bibako can eat the macarons numbered $1, 4$.
For query $2$, there is only $1$ macaron of flavor $3$, so the condition cannot be achieved.
For query $3$, no macaron of flavor $5$ exists, so the condition cannot be achieved.
This sample input satisfies the constraints of Subtasks 2,4.
Sample 2
Input
1 1 1 1 1 1 1
Output
No
This sample input satisfies the constraints of all subtasks.
License and Credits:
The characters "Bitaro" and "Bibako" appearing in this problem are derivative works based on the character settings in problem statements published by the Japanese Committee for the International Olympiad in Informatics.
This problem statement is published under CC BY-SA 4.0 (Attribution-ShareAlike 4.0 International) in accordance with the original author's license.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。