thx

it's the number of swaps in a bull sort.

Edited by author 03.08.2011 02:27

i don't understand you, pls ubderstand and give me some hints

Hey, I got TLE on this code with O(k*n*lgn) using Indexed trees. My code is attached for reference:

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int bit[10001];
bool myfunc(vector<int> a,vector<int> b)
{
 if(a[0]>b[0])
 return true;
 return false;
}
void update(int x,int n)
{
     int i;
     for(i=x;i<=n;i+=i&-i)
     bit[i]++;
}
int getval(int x)
{
 int i,ans=0;
 for(i=x;i>0;i-=i&-i)
 ans=ans+bit[i];
 return ans;
}
main()
{
      int n,k,ans=0,ind;
      scanf("%d %d",&n,&k);
      int cas=1;
      while(k--)
      {
       int i;

       vector<vector<int> > arr;
       vector<int> emp;
       arr.clear();
       for(i=0;i<n;i++)
       {
        arr.push_back(emp);
        arr[i].push_back(0);
        scanf("%d",&arr[i][0]);
        arr[i].push_back(i+1);

       }
       sort(arr.begin(),arr.end(),myfunc);
       memset(&bit,0,sizeof(bit));
//       cout<<bit[1]<<endl;
       int val=0;
       for(i=0;i<n;i++)
       {
//        cout<<arr[i][1]<<" ";
//cout<<val<<" ";
        val=val+getval(arr[i][1]);
        update(arr[i][1],n);

       }
//       cout<<endl;

       if(ans<val)
       {ans=val;ind=cas;}
       cas++;
      }
      printf("%d",ind);
//      cin>>ind;
}


Any hints?