KDOMINO - K-dominant array

no tags 

Professor Mahammad was sitting in his garden when an apple fell on his head, and in a stroke of brilliant insight, he suddenly came up with K-dominant notation. An array with length L is called K-dominant, if and only if there is at least one element x lying in the array for which occurence(x) * K >= L. After analyzing several arrays with this property, professor now, made up a new problem for you. Your task is simple, there are given an array of length N and several queries. For each of the queries, you just need to check whether the subarray [l, r] is k-dominant or not.


The first line of the input contains two positive integers N and Q, the number of elements of the array and the mean, respectively. (N, Q ≤ 200000).

The following line contains N integers which represent elements of the array.

The following Q lines contains three integers l, r, and k. (1 ≤ l ≤ r ≤ N).

All the numbers in the input section are 32-bit positive integers.

Sum of all k's in queries does not exceed 500000.


For each of the queries, print per line YES or NO if there is an element lying in the subarray which satisfies the condition in the statement.


8 3
1 4 2 3 2 2 5 3
2 6 2
1 8 2
1 8 3

Note: For the first and third queries x = 2 satisfies the condition. And for the second query there is no element for which the condition holds true.



hide comments
kyrillos: 2018-05-20 17:41:24

O(N*sqrt(N)*log(N)) will not pass try to optimize it to O(N*sqrt(N))

swapnil_007: 2017-10-09 06:47:09

Last edit: 2017-10-10 21:55:44
julkas: 2017-10-08 14:34:23

@swapnil_007. My offline solution passed. And FREQ2. Try first FREQ2.

Last edit: 2017-10-08 14:39:17
swapnil_007: 2017-10-08 11:35:54

Will O(N*sqrt(N)*log(N)) pass?

wisfaq: 2017-10-04 20:13:43

Last edit: 2017-10-04 20:14:04
Min_25: 2017-10-02 18:37:37

@Blue.Mary: Yes.

By the way, this problem is almost the same as http://www.spoj.com/problems/FREQ2/.
re: so sorry for similarity, we still work on making the problem in a way that it can not be solved by the same simple idea.

Last edit: 2017-10-03 13:11:29
[Rampage] Blue.Mary: 2017-10-02 17:30:20

Does 1 <= l <= r <= N hold for all test cases?
re: yes, let me correct it.

Last edit: 2017-10-02 18:43:00

Added by:mahmud2690
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Me, MYSELF & I