KDOMINO - K-dominant array
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.
Input: 8 3 1 4 2 3 2 2 5 3 2 6 2 1 8 2 1 8 3
Output: YES NO YES
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.
O(N*sqrt(N)*log(N)) will not pass try to optimize it to O(N*sqrt(N))
Last edit: 2017-10-10 21:55:44
@swapnil_007. My offline solution passed. And FREQ2. Try first FREQ2.Last edit: 2017-10-08 14:39:17
Will O(N*sqrt(N)*log(N)) pass?
Last edit: 2017-10-04 20:14:04
Does 1 <= l <= r <= N hold for all test cases?