Getting tle for spoj XMEN even after nlogn lis implementation!

general
, , ,
1

Here is my implementation of the nlogn complexity of Lis:
Solution

2

Sometimes it happens on SPOJ that time limit for JAVA/Python are very strict ( more than they should be ). You should try submitting the problem in c++ to confirm that you’re not facing this issue.

3

X-MEN problem on spoj is really very nice example of relation between LCS and LIS. Here we have to perform LCS on two given array but for given constraint n<=10^5, it gives TLE with LCS because it is of O(n^2) time complexity. So we have to convert this problem into LIS and solving it with O(nlogn) complexity.
You can refer editorial of ACMICL4 for this understanding link provided here.
Refer GeeksforGeeks for understanding LCS and LIS link text.