@Anshuman sir There is mistake in above code : u wrote -->> " ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1); " I think it should be -->> "ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (IN[i]- L[IN[i]] + 1);
correct me if i m wrong !!!! On May 26, 9:17 am, anshu mishra <[email protected]> wrote: > L[i] tells how many elements D[j] less than D[i] such that j < i ; > for this u have to use BIT, segment tree, or any balanced BST(balanced > implies to avoid the worst case that is o(n^2)); > > rem = n; > curtime = 0; > last = 0; > for (i = 0; i < n;) > > ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1); > curtime += (D[i] - last) * rem; > i++; > rem--; > while (i < n && D[i] == D[i-1]) > { > ans[IN[i]] = ans[IN[i-1]] + 1; i++; > rem--; > } > last = d[i-1]; > > } > > curtime = total time till the iteration in which last event(which has burst > time just less than current event) has been completed. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
