Cod sursa(job #2277928)

Utilizator livliviLivia Magureanu livlivi Data 7 noiembrie 2018 02:24:03
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<fstream>
#define N 800
#define B 60000
#define d(x) x&(-x)
using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

int v[N + 1];
int AIB[B + 1];

void updateAIB(int x){
	for(; x <= B; x += d(x))
		AIB[x]++;
}

int queryAIB(int x){
	int ans = 0;

	for(; x > 0; x -= d(x))
		ans += AIB[x];

	return ans;
}

int main(){
	int n;
	cin>>n;

	for(int i = 0; i < n; i++){
		cin>>v[i];
		updateAIB(v[i]);
	}

	int ans = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if (i != j) ans += (queryAIB(v[i] + v[j]) - queryAIB(abs(v[i] - v[j]) - 1) - 2);

	cout<<ans / 3<<endl;
	return 0;
}