TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.0% (81/90)

Submission's AC Ratio

21.0% (186/887)

Tags

Description

甦蹦這幾天心急如焚!因為他的傳說中的橘子遇到了蟲害!

而且並不是一種蟲,是很多種蟲混雜入侵了橘子園。
如今是決戰的時刻,害蟲們在籬笆前一字排開,準備對橘子園進行總攻擊。

甦蹦腦袋裡想到了一句話,擒賊先擒王。
沒錯,要擊倒害蟲聯軍,就要先把領導的蟲種族找出來。當然,也可能沒有領導種族。

對於每個區段[L, R]的害蟲們,會有一個領導係數K,
表示如果有一種蟲在這個區段內出現大於等於(區段長/K)隻,
那麼代表該區段有領導種族;反之則表示該區段僅是一盤散沙。

現在書蹦想瞭解每個指定區段是否有領導種族,請你幫他解決這個問題吧。

Input Format

輸入第一行有兩個數字N, Q,表示害蟲的數量跟詢問個數。(害蟲編號為1~N)
接下來有一行有N個數字,依序代表每隻害蟲的種族。
接下來會有Q行,每行有三個數字L, R, K,表示區段[L, R]的領導係數為K。

保證N ≤ 50,000,所有詢問的K值總和不超過100,000。

Output Format

輸出包含Q行,每行僅一個字串"Yes"或"No"表示該區段是否有領導種族。

Sample Input 1

5 3
1 2 2 1 3
1 3 2
1 5 2
1 5 3

Sample Output 1

Yes
No
Yes

Hints

第一筆詢問區間為{1, 2, 2},係數為2。所以害蟲2為領導。
第二筆詢問區間為{1, 2, 2, 1, 3},係數為2。所以沒有任何一個領導。
第三筆詢問區間為{1, 2, 2, 1, 3},係數為3。害蟲1和2都是領導。

甦蹦就算知道了有無領導種族但還是無力對抗害蟲大軍,甦蹦只好前往古墨西哥神殿尋求遠古先靈的協助。於是各路英豪都聚在一起了……

Problem Source

原TIOJ1699 / ABCLS Contest, Problem I

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10