When I replaced cout with printf in my code, I got AC!! I Should have tried
it earlier itself..
On Fri, May 13, 2011 at 11:51 AM, anshu mishra <anshumishra6...@gmail.com>wrote:
> no all these data structure also take time O(nlogn)
>
> solving this problem using segment tree
>
> map all elements to its index on the sorted array.
>
> ex. 2 3 8 6 1 --> 1 2 4 3 0
>
> intialiize all element in segment tree wid zero
>
> start from the last index of array
>
> whenever u visit a node increase its value by 1 --> one more value came in
> this range
>
> if u have go right child then increase the count by number of element in
> left child(that is value left node). thats it;
>
> void query(int a, int s, int e, int node, unsigned long long &count)
> {
> int mid = (s+e)>>1;
> tree[node] += 1;
> if (s == e) return;
> if (a <= mid)
> {
> query(a, s, mid, (node<<1)+1, count);
> }
> else
> {
> count += tree[(node<<1)+1];
> query(a, mid+1, e, (node<<1)+2, count);
> }
> return;
> }
>
> I have written another code using ur logic its giving correct answer. I m
> not getting where u r wrong. :P
>
> #include <stdio.h>
>
> unsigned long long int merge_and_count (int *a, int start, int mid, int
> end)
> {
> int len_a = mid - start + 1;
>
> int len_b = end - mid;
> int C[end - start + 1];
> int k = 0;
> int i = start;
> int j = mid + 1;
> unsigned long long int count = 0;
> int rem = len_a;
>
> while ( i <= mid && j <= end ) {
>
> C[k++] = a[i] < a[j] ? a[i] : a[j];
> if ( a[j] <= a[i] ) {
> count += rem;
> j++;
> } else {
> i++;
> rem--;
> }
> }
>
> while ( i <= mid ) {
> C[k++] = a[i++];
> }
>
> while ( j <= end ) {
>
> C[k++] = a[j++];
> }
>
> for ( i = start; i <= end; i++ ) {
> a[i] = C[i-start];
> }
>
> return count;
> }
>
> unsigned long long int sort_and_count(int *a, int start, int end)
> {
> int mid;
>
> unsigned long long int rA, rB, r;
>
> if ( end == start )
> return 0;
> else {
> mid = (start + end) >> 1;
> rA = sort_and_count (a, start, mid);
> rB = sort_and_count (a, mid + 1, end);
> r = merge_and_count (a, start, mid, end);
>
> } return (rA+rB+r);
> }
>
> int main()
> {
> int t, n, i;
> int a[200100];
>
>
> scanf ("%d", &t);
>
> while ( t-- ) {
> scanf ("%d", &n);
>
>
> for ( i = 0; i < n; i++ ) {
>
> scanf ("%d", &a[i]);
> }
>
> printf ("%llu\n", sort_and_count(a, 0, n - 1));
> }
>
> return 0;
>
> }
>
>
> --
> 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.
>
--
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.
