KTH_INDEX - Solution to all the problems
People have been coming to the wise man, complaining about the same problems every time.
One day he told them a joke and everyone roared in laughter.
After a couple of minutes, he told them the same joke and only a few of them smiled.
When he told the same joke for the third time no one laughed.
The wise man smiled and said:
"You can't laugh at the same joke over and over. So why are you always crying about the same problem?"
He has also created a very simple game to cheer the people up. The game is as follows:
You are given a sequence A of N integers.
The task is to answer Q queries on the given sequence. For each query, you will be given four space-separated integers L, R, P, K.
Print the index of Kth occurrence of P in L to R(inclusive). If no such index exists, print -1.
Input
The first line contains two space-separated integers N and Q.
The second line contains N space-separated integers. (1-based indexing)
Following Q lines contain,
Four integers L, R, P, K.
Output
For each query, print a single line containing one integer between 1 to N i.e. index of the Kth occurrence of P in L to R.
Print -1 if no such index exists.
Constraints
2 ≤ N, Q ≤ 105
1 ≤ Ai ≤ 106
1 ≤ L < R ≤ N
1 ≤ P ≤ 106
1 ≤ K ≤ N
Example
Input: 10 3 1 1 2 1 2 3 1 2 3 4 1 10 2 3 1 5 2 3 5 9 3 2 Output: 8 -1 9
hide comments
shoaib_ali_34:
2022-01-08 14:45:38
i SOLVED this in O(n) in java , its giving TLE. |
|
Waseem Ahmed:
2021-09-23 14:24:15
Nice problem. A little thinking needed about the appropriate data structures to use. That's all. |
|
Jean-Ralph Aviles:
2021-08-29 16:36:13
Time limits are VERY tight. I had to micro-optimize a O(q*log(n) + n) solution for it to AC. |
|
sahil_19:
2020-05-21 05:20:39
I am using linear search but getting TLE |
|
[Lakshman]:
2020-02-10 20:43:09
@sahil1422 My Solution is not a brute force rather its a badly written Java code. I think need to check my CPP version.
|
|
sahil1422:
2020-02-10 07:25:28
Yes, I changed the test data after a week so as to stop the brute solutions. I realised later that brute solutions are getting AC. Sorry for the inconvenience caused. |
|
nadstratosfer:
2020-02-05 23:48:15
Lakshman, I just resubmitted my 0.16s solution that originally got AC on the day of publication, and it came in at 0.15s. |
|
[Lakshman]:
2020-02-05 12:10:46
@Problem setter Did you change the Test data set ? Because my earlier accepted solution got TLE. Its no a good idea to update the test date after problem is publish . I did not see any warning or comment from you. |
|
:D:
2019-11-21 13:27:55
Great problem. it's easy but fun and, as such, a great entry point for people new to query problems. |
|
sriram_21:
2019-11-19 14:20:35
Good problem constraints made it possible for me!!!
|
Added by: | Sahil |
Date: | 2019-11-15 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |