Cod sursa(job #1552223)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 17 decembrie 2015 15:03:34
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

int v[100005];

int binarySearch(int x, int s, int n){
    int step = 1<<16;
    for(s--;step;step >>= 1){
        if(s+step <= n && v[s+step] <= x){
            s += step;
        }
    }
    return s;
}

int main()
{
    int n,m,type,x,i,ans,j,poz1,poz2;
    int poz;
    freopen("cautbin.in", "r", stdin);// !!! nrtri !!!
    freopen("cautbin.out", "w", stdout);
    scanf("%d",&n);
    for(i = 1;i <= n;i++){
        scanf("%d",&v[i]);
    }
    sort(v+1,v+n+1);
    ans = 0;
    for(i = 1;i <= n;i++){
        for(j = i+1;j <= n;j = poz+1){
            poz1 = binarySearch(v[i]+v[j]+1, j+1, n);
            poz2 = binarySearch(v[j]-v[i], j+1, n)+1;
            ans = ans + (poz1-poz2+1);
        }
    }
    printf("%d",ans);
    return 0;
}