Cod sursa(job #703589)

Utilizator stefanzzzStefan Popa stefanzzz Data 2 martie 2012 12:59:50
Problema Numarare triunghiuri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");

int n,v[801], nrl[30001];
long long S;

void qsort(int p, int q);
int divide(int p, int q);

int main()
{
    int i,j;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    qsort(1,n);
    for(i=1;i<=n;i++){
        nrl[v[i]]=nrl[v[i]-1]+1;
        for(j=v[i]+1;j<v[i+1];j++)
            nrl[j]=nrl[v[i]];}
    for(j;j<=v[n]+v[n-1];j++)
        nrl[j]=nrl[j-1];
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
            if(v[j]-v[i]>=v[j])
                S+=nrl[v[i]+v[j]]-nrl[v[j]-v[i]-1];
            else
                S+=nrl[v[i]+v[j]]-nrl[v[j]];}}
    g<<S;
    f.close();
    g.close();
    return 0;
}

void qsort(int p, int q){
    int m=divide(p,q);
    if(m>p+1)
        qsort(p,m-1);
    if(m<q-1)
        qsort(m+1,q);}

int divide(int p, int q){
    int st=p, dr=q, x=v[p];
    while(st<dr){
        while(st<dr&&v[dr]>=x)dr--;
        v[st]=v[dr];
        while(st<dr&&v[st]<=x)st++;
        v[dr]=v[st];}
    v[st]=x;
    return st;}