MKTHNUM from SPOJ--help required

merge
sort
tree

#1

question link : http://www.spoj.com/problems/MKTHNUM/
my code link : https://ideone.com/JLNF6b
im getting TLE…donno whether my logic is correct or not…!!
if wrong pls correct …if correct help me in getting a decent approach !!
thanks in advance : )


#2

I suspect that its the merging of vectors thats giving you TLE. It depends on linearly on size of vector (afaik) and can cause a TLE if limit is strict. I am looking at possible approaches.


#3

Is my logic correct bro @vijju123 ??


#4

The logic seems correct bro. Just try to get around without using vectors. Also, I think concept of persistence is required.


#5

how can we solve it using persistant segment tree ??