Most Frequent Element
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Given an array of size n, you have to answer queries of the form : L R k . For each query, you have to find an element which occurs consecutively in the subarray [L,R] more than or equal to k times. k will always be greater than floor((R-L+1)/2). If no such element exists, print -1.
First line of the input contains 2 space separated N and M, denoting the size of the array and the number of queries.
The next line contains N space separated integers, where the i-th integer Ai denotes the ith element of the array.
Each of the next M lines contains 3 integers space separated integers L, R and k.
Output M lines where each line contains the answer to the i-th query.
- 1 ≤ N, M ≤ 105
- 1 ≤ L ≤ R ≤ N
- floor((R-L+1)/2) < k ≤ R-L+1
- 0 ≤ Ai ≤ 109
Subtask #1 (10 points):
- 1 ≤ Ai ≤ 3
- 1 ≤ M ≤ 10
Subtask #2 (30 points):
- 1 ≤ N ≤ 1000
Subtask #3 (60 points):
- No other constraints
Input: 5 1 1 2 2 2 2 1 5 3 Output: 2
The element 2 occurs more than 3 times in the range [1,5].
|Tags||ad-hoc, implementation, kevind|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.