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.
