Cod sursa(job #1205206)

Utilizator tudorv96Tudor Varan tudorv96 Data 5 iulie 2014 17:53:24
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#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;
}