Pagini recente » Cod sursa (job #2120241) | Cod sursa (job #1533551) | Cod sursa (job #135281) | Cod sursa (job #3202388) | Cod sursa (job #1205206)
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
const int Lg = 6e5 + 5;
int v[Lg / 2], aib[Lg], n, sol;
void update(int i) {
while (i < Lg) {
aib[i]++;
i += (i^(i-1)) & i;
}
}
int sum(int i) {
int s = 0;
while (i > 0) {
s += aib[i];
i -= (i^(i-1))& i;
}
return s;
}
int main() {
fin >> n;
for (int i = 0; i < n; ++i)
fin >> v[i];
sort (v, v + n);
for (int i = 0; i < n; ++i) {
sol += (i * (i - 1)) / 2 - sum(v[i] - 1);
for (int j = 0; j < i; ++j)
update (v[i] + v[j]);
}
fout << sol;
}