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 <[email protected]> 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 <[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.
