https://codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

Explanation: Coming soon

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

#include <algorithm>
#include <stdint.h>

#define DEBUG 0

#if DEBUG
#   define LOG(...) printf(__VA_ARGS__)
#else
#   define LOG(...)
#endif

struct Point {
    Point(int64_t pos, int left)
    {
        this->pos = pos;
        this->left = left;
    }
    
    void log_point()
    {
        LOG("%s:%d ", left == 1 ? "l" : "r", pos);
    }
    
    int64_t pos;
    int left;//0 = right of disc, 1 = left of disc
};

bool compare_point(const Point& l, const Point& r)
{
    if (l.pos == r.pos)
    {
        return l.left > r.left;//the left point of a disc should come before the right point of another disc 
    }
    
    return l.pos < r.pos;
}

int solution(vector<int> &A) {
    if (A.size() == 0)
        return 0;
    // write your code in C++14 (g++ 6.2.0)
    //list of left and right points of every discs
    vector<Point> points;
    points.reserve(A.size() * 2);
    
    for (int i = 0; i < (int)A.size(); ++i)
    {
        int64_t left = (int64_t)i - A[i];
        int64_t right = (int64_t)i + A[i];
        
        points.push_back(Point(left, 1));
        points.push_back(Point(right, 0));
    }
    
    //sort the points
    sort(points.begin(), points.end(), compare_point);
    
    #if DEBUG
    for (auto& p: points)
    {
        p.log_point();
    }
    LOG("\n");
    #endif
    
    //interate through the points
    int current_discs = 1;
    uint64_t num_intersected = 0;
    auto p_ite = points.begin();
    ++p_ite;
    for (; p_ite != points.end(); ++p_ite)
    {
        LOG("At: "); p_ite->log_point(); LOG("\n");
        if (p_ite->left)
        {
            current_discs ++;
            int new_intersecs_at_this_point = current_discs - 1;
            num_intersected +=  new_intersecs_at_this_point;
            LOG("--> new number of intersections=%d (total=%lu)\n", new_intersecs_at_this_point, num_intersected);
            
            if (num_intersected > 10000000)
                return -1;
        }
        else {
            current_discs --;
        }
        
        LOG("current discs = %d\n", current_discs);
    }
    
    return (int)num_intersected;
}