TopCoder

User's AC Ratio

91.7% (22/24)

Submission's AC Ratio

21.1% (43/204)

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

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

Sample Output

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 65536
1 1500 65536 65536
2 1500 65536 65536
3 1500 65536 65536
4 1500 65536 65536
5 1500 65536 65536
6 1500 65536 65536
7 1500 65536 65536
8 1500 65536 65536
9 1500 65536 65536