aman_naughty's blog

By aman_naughty, history, 5 years ago, In English

Problem link : link

code : link

I am considering each element as a maximum element and then determining the size of the subarray in which that element can be maximum. If x is my maximum element and y is my minimum element in the optimal subarray, then we have (x-y)<B which implies that my y should be -> x-B< y <= x . Now I store the elements in a vector of pair where the first element is the element at index i and the second element is the index i. Then I sort it based on the first element. After that, I build a segment tree on the modified index array to get the maximum and minimum index of y which will then determine our ans.

In other words, if v[i] is my maximum element of the optimal subarray I need to find the maximum and minimum index of an element in the entire array which has a value y satisfying v[i]-B< y <=v[i]. For this purpose, I am using a segment tree to store the maximum and minimum index in a range and that range I am finding with the help of lower_bound and upper_bound.

If you look at the code maybe you can understand what I am trying to say.

This is giving wrong answer.

Can someone please help me, whether my approach is wrong or am I doing some implementation mistake.

Sorry for poor explanation of my code .

  • Vote: I like it
  • -6
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, someone, help me .....

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The best advice I can offer you — random test case + brute force to check the correctness of your algo. Come on. Don't be lazy. If you still cannot find a case that breaks your code, I can consider helping you.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

There is no need of segment tree or something that, this problem more related to two pointers

I used multiset, and AC this problem

Add to multiset element $$$a[i]$$$ and erase elements from the left while the difference between the biggest and smallest element in array more than $$$b$$$, and the longest subarray with $$$max-min >= b$$$ in current state will be size of this multiset. Time complexity : $$$O(nlog(n))$$$

The solution code