circles.cpp

circles.cpp

#include <vector>

using namespace std;

struct UpDown
{
    UpDown(int in, int out)
        : in_(in)
        , out_(out)
    {}

    int in_;
    int out_;
};

typedef vector< UpDown > Histogram;

int number_of_disc_intersections( const vector<int> &A )
{
    if (A.empty()) return 0;
  
    Histogram hist(A.size(), UpDown(0, 0));
    for (int idx = 0; idx < (int)A.size(); ++idx)
    {
        hist[ max(0, idx - A[idx]) ].in_++;
        hist[ min((int)A.size()-1, idx + A[idx]) ].out_++;
    }

    int intersections = (hist[0].in_*(hist[0].in_-1)) >> 1;
    int circles = hist[0].in_ - hist[0].out_;
    for (int idx = 1; idx < (int)(A.size()); ++idx)
    {
        intersections += (hist[idx].in_*(2*circles + hist[idx].in_ - 1) >> 1);

        circles += (hist[idx].in_ - hist[idx].out_);
    }

    return ((intersections <= 10000000) ? intersections : -1);
}