[ create a new paste ] login | about

Link: http://codepad.org/u3bz02YK    [ raw code | fork ]

azure97 - C++, pasted on Dec 27:
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

const int MAXN = 20005;
const int MAXX = 100000;

int BIT[2][MAXX + 5]; // index 0 untuk kiri, 1 untuk kanan
int n,tc;
int arr[MAXN];

void Update(int id,int x,int val){
 for( ; x <= MAXX ; x += x & -x)
    BIT[id][x] += val;
}

int Query(int id,int x){
 int res = 0;
 for( ; x > 0 ; x -= x & -x)
    res += BIT[id][x];
  return res;
}

int main(){
 scanf("%d",&tc);
 while(tc--){
    memset(BIT,0,sizeof BIT);
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++){
        scanf("%d",&arr[i]);
        Update(1, arr[i], 1);
    }
    LL ans = 0;
    for(int i = 0 ; i < n ; i++){
        Update(1, arr[i], -1);

        int val1 = Query(0,arr[i] - 1);
        int val2 = Query(0,MAXX) - Query(0,arr[i]);

        int val3 = Query(1,arr[i] - 1);
        int val4 = Query(1,MAXX) - Query(1,arr[i]);

        ans += val1 * val4;
        ans += val2 * val3;
        Update(0, arr[i], 1);
    }
   printf("%lld\n",ans);
 }
 return 0;
}


Create a new paste based on this one


Comments: