Cod sursa(job #1480240)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 2 septembrie 2015 12:30:33
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>

const char iname[] = "nrtri.in";
const char oname[] = "nrtri.out";
const int MAXN = 805;

int n, a[MAXN], b[MAXN];

void read(){
    freopen(iname, "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", a+i);
}
void merge_sort(int st, int dr){
    if(st != dr){
        int mid = (st + dr) >> 1;
        merge_sort(st, mid);
        merge_sort(mid+1, dr);
        for(int i = st, k = st, j = mid+1; j<=dr || i <= mid;)
            if((j>dr) || ((i<=mid) && (a[i] < a[j])))
                b[k++] = a[i++];
            else
                b[k++] = a[j++];
        for(int i = st; i <= dr; ++i)
            a[i] = b[i];
    }
}
int lowBound(int p, int q){
    int lo, hi, mid;
    int x = a[p], y = a[q];
    for(lo = q+1, hi = n-1, mid = lo + ((hi - lo) >> 1); lo < hi; mid = lo +((hi - lo) >> 1)){
        if(x+y >= a[mid]){
            if((x+a[mid] >= y) && (y+a[mid] >= x)) hi = mid;
            else lo = mid + 1;
        }
        else hi = mid-1;
    }
    if((!(x+y>=a[lo]))||(!(x+a[lo] >= y)) || (!(y+a[lo] >= x)))
        return -1;
    return lo;
}
int uppBound(int p, int q){
    int x = a[p], y = a[q];
    int lo, hi, mid;
    for(lo = q+1, hi = n-1, mid = lo + ((hi-lo+1) >> 1); lo < hi; mid = lo + ((hi-lo+1)>>1)){
        if(x+y < a[mid])
            hi = mid - 1;
        else if((x+a[mid] >= y) && (y+a[mid]>=x)) lo = mid;
        else lo = mid + 1;
    }
    if(x+y < a[lo]) return -1;
    return lo;
}
void solve(){
    int ans = 0;
    for(int i = 0; i < n-1; ++i)
        for(int j = i+1; j < n; ++j){
            int pozMin = lowBound(i,j);
            if((pozMin >= 0) && (pozMin != j) && (pozMin != i)){
                int pozMax = uppBound(i, j);
                if(pozMax != j && pozMax != i){
                    ans += pozMax - pozMin + 1;
                    }
            }
        }
    freopen(oname, "w", stdout);
    printf("%d", ans);
}
int main()
{
    read();
    merge_sort(0,n-1);
    solve();
    return 0;
}