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.
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.
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.
2 ≤ N, Q ≤ 105
1 ≤ Ai ≤ 106
1 ≤ L < R ≤ N
1 ≤ P ≤ 106
1 ≤ K ≤ N
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
I am using linear search but getting TLE
@sahil1422 My Solution is not a brute force rather its a badly written Java code. I think need to check my CPP version.
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.
Lakshman, I just resubmitted my 0.16s solution that originally got AC on the day of publication, and it came in at 0.15s.
@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.
Great problem. it's easy but fun and, as such, a great entry point for people new to query problems.
Good problem constraints made it possible for me!!!