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; }