Yath's blog

By Yath, history, 16 months ago, In English

For this problem : https://www.spoj.com/problems/HAYBALE/ I submitted this solution: https://onlinegdb.com/-0MA4LwEE . This solution is giving TLE i.e. why I want to know the time complexity(with explanation).
My logic was to store all the K pairs in a map<int , vector> such that the first element of each pair acts as key , its value being a vector of all the values the key is making a pair with. Now I iterate from 1 till N(stack) and for each stack , I iterate through the keys which are less than or equal to the position of that stack . For each key , I binary search to find out In how many pairs my current stack is falling into. Finally I sort the array and the find the median.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$O(N*K*logK)$$$