Cod sursa(job #2203873)

Utilizator DordeDorde Matei Dorde Data 13 mai 2018 15:51:59
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <iostream>
using namespace std;
char const in [] = "nrtri.in";
char const out [] = "nrtri.out";
int const NM = 5e5 + 7 , BUFF = 1e7;
int heap [NM] , n , point;
char buff [BUFF];
int getbuff ()
{
    int val = 0;
    while(! isdigit (buff [point]))
    {
        ++ point;
        if(point == BUFF)
        {
            point = 0;
            fread (buff , 1 , BUFF , stdin);
        }
    }
    while(isdigit (buff [point]))
    {
        val = val * 10 + (buff [point] - '0' );
        ++ point;
        if(point == BUFF )
        {
            point = 0;
            fread (buff , 1, BUFF , stdin);
        }
    }
    return val;
}
int father (int nod)
{
    return nod / 2;
}
int left_son (int nod)
{
    return nod * 2;
}
int right_son (int nod)
{
    return nod * 2 + 1;
}
void sift (int strat)
{
    int son = 1;
    while(son)
    {
        son = 0;
        if(left_son (strat) <= n)
        {
            son = left_son (strat);
            if(right_son (strat) <= n && heap [son] < heap [right_son (strat)])
                son = right_son (strat);
            if(heap [son] <= heap [strat])
                son = 0;
        }
        if(son)
        {
            swap (heap [son] , heap [strat]);
            strat = son;
        }
    }
}
void heapsort ()
{
    int i;
    for(i = n ; i > 0 ; -- i)
    {
     //   printf ("%d " , heap [1]);
        swap (heap [1] , heap [n]);
        -- n;
        sift (1);
    }
}
int search_ (int x , int from , int to)
{
    int found = -1;
    while(from <= to)
    {
        int m = (from + to) / 2;
        if(heap [m] <= x)
        {
            found = m;
            from = m + 1;
        }
        else
            to = m - 1;
    }
    return found;
}
int main()
{
    int i;
    freopen (in , "r" , stdin);
    freopen (out , "w" , stdout);
    fread (buff , 1 , BUFF , stdin);
    n = getbuff ();
    int nx = n , j , best = 0;
    for(i = 1 ; i <= n ; ++ i)
        heap [i] = getbuff ();
    for(i = n / 2 ; i > 0 ; -- i)
        sift (i);
    heapsort ();
    n = nx;
    for(i = 1 ; i < n ; ++ i )
        for(j = i + 1 ; j <= n ; ++ j)
        {
            int x = search_ (heap [i] + heap [j] , j + 1 , n);
            if(x != -1)
                best += (x - j);
        }
    printf ("%d" , best);
    return 0;
}