SMARKET - Editorial

See my solution - CodeChef: Practical coding for everyone

The solution is accepted using Segment tree where each node is storing the sorted list of elements in the range (this is basically a merge sort tree ). Make sure to use vectors while creating segment tree nodes and donā€™t pass vectors in function but instead pass their references. I got many TLEā€™s because of it.
My solution using Segment trees - Solution

I did everything in O(n+q) by pushing queries into a vector at location l and r and processing with line sweep

Credits to bluescorp for sharing a unique observation, we both had a O(Q*logN) algorithm ready before we communicated.
My solution(AC 0.23s): CodeChef: Practical coding for everyone

Do i get stars now? :smiley:

i cant delete my comment so im doing this instead ;_;
get my solution on the first page plx XD

Yeah, seems like a typo.

given K = 2
Let say my bucket(which is completely lie in the range [L , R] ) contain values like this -
12 12 12 3 3 12 12 12 and after sorting the values in bucket are - 12 12 12 12 12 12 3 3

and from your above statement by doing binary search (in this bucket) , I have only 2 values which occur at least K (ie K = 2 )times , but answer should be 3 isnā€™t it ?

@rahulmysuru7 please help .

which array a ? given A or the array we make array B ?

also -

B will be [1,2,3,1] isnā€™t it or I did mistake ?

Can anyone provide \sqrt(n) log(n) solution using only SQRT decompostion not BIT.

u r not sorting the values, u are sorting the size of buckets, the size of buckets is 3,2,3 after sorting you get 2,3,3. now binary search will give you the answer(upper bound on k=1)

what do u mean by we are sorting size of buckets , all buckets are of root(n) except last (may be) .

Please explain with given Test case . using only SQRT .

8 5
20 10 10 10 7 7 7 10
2 6 2
3 6 2
3 6 3
3 8 3
3 8 1

ahh, lol i was using seg tree method,but it applies the same way for sqrt decomposition as well. @ssrivastava990

By bucket i mean the length of consecutive repeating element , in ur example 12 12 12 3 3 12 12 12,. U have 3 12s, 2 3s and 3 12s. So u store 3,2,3 .sort them , u get 2,3,3

for this let I explain u and tell me whether I m correct or not -

A = 20 10 10 10 7 7 7 10
B = 1 1 2 3 1 2 3 1

Now we make blocks of size 2
1 1 , 2 3 , 1 2 , 3 1

sort each block

1 1 , 2 3 , 1 2 , 1 3

Now ?

Ur sqrt decomposition will look like this
ur 4 blocks
20 10 | 10 10 | 7 7 |7 10
now first block has 2 elements with k=1, u store the values of k and sort them and the first and last element of each of the block,
so it looks like this
1 1 | 2 | 2 | 1 1
first last element part will be as this shown below,
20 10 | 10 10 | 7 7 |7 10
if last element of previous block matches with the first element of next block , u consider the length values from left and right for that if both were greater than k ,u reduce 1 from total, else if one of them was greater ,do nothing , else if total length greater than k ,add 1, else do nothing

for ur query 2 6 2 last element of 1st block matches with first element of 2nd block ,do as above and continue to get total, and only for the first and last block u traverse the range rest all blocks u already have the answer.

Thanks , I will try , let see able to solve or not :pray: