Cod sursa(job #2545829)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 13 februarie 2020 16:17:39
Problema Numarare triunghiuri Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int aib[30005],v[1005],x,y,n,nr;
int ub(int x)
{
    return (x&(-x));
}
void update(int x)
{
    for(int i=x;i<=30000;i+=ub(i))
        aib[i]++;
}
int query(int x)
{
    int s=0;
    for(int i=x;i>=1;i-=ub(i))
    {
        s+=aib[i];
    }
    return s;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
        update(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(v[i]>v[j])
            {
                x=v[i]-v[j];
                y=v[i]+v[j];
            }
            else if(v[i]<v[j])
            {
                x=v[j]-v[i];
                y=v[j]+v[i];
            }
            else
            {
                x=1;
                y=v[j]+v[i];
            }
            nr+=query(y)-query(x-1);
            if(v[i]>=x && v[i]<=y)
                nr--;
            if(v[j]>=x && v[j]<=y)
                nr--;
        }
    }
    g<<nr/3<<'\n';
    return 0;
}