Pagini recente » Cod sursa (job #2959118) | Cod sursa (job #2940715) | Cod sursa (job #159408) | Cod sursa (job #2896013) | Cod sursa (job #2203873)
#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;
}