Problema Inversiones (AC) - IOI-Etapa1-Problemset15 [Optimizar Solución]

gistfile1.cpp

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz size
using namespace std;
typedef long long int lli;

int C,N;
lli Limite = 0;
lli AC = 0;
pair<int, int> A[1000002];
int BIT[1000015]={0};

void update(int idx, int val){
	while(idx<=Limite){
		BIT[idx]+=val;
		idx += (idx&-idx);
	}
}

lli query(int idx){
	lli sum = 0;
	while(idx){
		sum += BIT[idx];
		idx -= (idx&-idx);
	}
	return sum;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int i,j,k,p;
    cin>>C;
    for(i=0; i<C; ++i){
        cin>>N;
        AC = 0;
        memset(BIT, 0, sizeof(BIT));
        for(j=1; j<=N; ++j){
        	cin>>A[j].X>>A[j].Y;
        	if(A[j].Y>Limite){
                      Limite = A[j].Y;
        	}
        }
        sort(A+1, A+N+1);
        for(j=N; j; --j){
        	update(A[j].Y, 1);
        	AC += query(A[j].Y-1);
        }
        cout<<AC<<"\n";
    }
    return 0;
}