wait !! wait !! @Anshuman sir...u have left few case ; I corrected ur code and got accepted at spoj.
Here is the correct code; //here F[] is array which got 3 fields ( element value(same as ur D[] array) , its index in original input(same as ur IN[] array) , number of elements less than it till its poistion in original array(same as ur L[] array) ) long long int rem = n; long long int curtime = 0; long long int last = 0; long long int *Ans = new long long int[n]; for(int i=0;i<n;){ Ans[F[i].idx] = curtime + ((long long int)(F[i].data-last-1))*rem + (long long int)(F[i].idx-F[i].rep+1); curtime += ((long long int)(F[i].data - last))*rem; i++; rem--; while(i<n && F[i].data == F[i-1].data){ Ans[F[i].idx] = Ans[F[i-1].idx] + (long long int)(F[i].idx - F[i-1].idx - (F[i].rep - F[i-1].rep)); i++; rem--; } last = (long long int)F[i-1].data; } On May 26, 8:15 pm, vishwakarma <vishwakarma.ii...@gmail.com> wrote: > @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 <anshumishra6...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.