first for every element get the number of element before its index have less
value.
example
L[] = 0 0 1 1 3
D[] = 8 1 3 3 8
IN[] = 0 1 2 3 4
you can use segment tree for this it will give solution in o(nlogn);
after that sort the array and start from 0th index
D[] = {1 3 3 8 8}
IN[] = {1 2 3 0 4}
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);
i++;
while (i < n && D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]]; i++;
}
curtime += (D[i] - last) * rem;
}
finally answer will be solution;
--
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.
