No.3705 ビバ子とマカロン (Bibako and Macaron)
Rapca1256
tomorunn注意
本問題の各テストケースあたりの実行制限時間は3.0secなので注意せよ.問題文
ビーバーのビ太郎とビバ子は $N$ 個のマカロンが入ったマカロンの箱詰めを購入した.
マカロンには $N$ 種類の味があり, $i$ 個目のマカロンは味 $A_i$ である. ($1 \le A_i \le N$)
$Q$ 個の独立した質問が与えられるので, それぞれに答えよ. $i$ 個目の質問は以下のとおりである.
- ビ太郎は味が $L_i$ 以上 $R_i$ 以下のマカロンを, ビバ子は味が $L'_i$ 以上 $R'_i$ 以下のマカロンを $1$ つずつ食べたいと思っている.
箱のマカロンをそれぞれが $R_i - L_i + 1$ 個、$R'_i - L'_i + 1$ 個ずつ重複なく選んで食べる方法であって, それぞれが食べたい味のマカロンをすべて食べる方法が存在するか判定せよ.
入力
$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$
制約
- $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$.
- 入力はすべて整数である.
部分点
この問題にはサブタスクによる部分点が設定されています。
| サブタスク名 | 配点 | 制約 |
|---|---|---|
| 小課題1 | 10%（20点） | $N \le 100, Q \le 100$, 各質問について, $L_i=R_i,L'_i=R'_i$. |
| 小課題2 | 30%（60点） | $N \le 100, Q \le 100$. |
| 小課題3 | 60%（120点） | 追加の制約はない. |
出力
$Q$ 行出力せよ.
$i$ 行目には, $i$ 個目の質問に対する答えが可能なら Yes を, そうでないなら No を出力せよ.
答え以外は何も出力しないこと．(入力を促す文章なども出力しないこと．)
サンプル
サンプル1
入力
6 1 3 2 2 1 4 3 2 4 1 2 1 4 2 3 1 5 1 1
出力
Yes No No
$1$ つ目の質問について, ビ太郎は $2, 3, 6$ 個目のマカロンを, ビバ子は $1, 4$ 個目のマカロンを食べればよい.
$2$ つ目の質問について, 味 $3$ のマカロンが $1$ つしかないので, 条件を達成することはできない.
$3$ つ目の質問について, 味 $5$ のマカロンが存在しないので, 条件を達成することはできない.
この入力例は小課題2,4の制約を満たす.
サンプル2
入力
1 1 1 1 1 1 1
出力
No
この入力例はすべての小課題の制約を満たす.
ライセンス・クレジット表記：
本問題に登場するキャラクター「ビ太郎」および「ビバ子」は、一般社団法人 情報オリンピック日本委員会が公開している問題文のキャラクター設定に基づいた二次創作です。
本問題文は、原著作者のライセンスに従い、CC BY-SA 4.0（表示 - 継承 4.0 国際）の下で公開されています。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。