PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Firstly we need disjoint the index of the houses for processing with only O(m) of houses, not O(n) of them, then the remains is only processing with segments which we can use some data structure like segment tree of binary indexed tree.
Complexity: O(m x log2 m)
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.