Points and segments solution Task:


  Given a set of points on a line and a set of segments on a line. The
  goal is to compute, for each point, the number of segments that
  contain this point.
  
  Input Format
  
  The first line contains two non-negative integers \$s\$ and \$p\$ defining the number of segments and the number of points on a
  line, respectively. The next \$s\$ lines contain two integers \$a_i, b_i\$
  defining the \$i\$th segment \$[a_i, b_i]\$. The next line contains \$p\$
  integers defining points \$x_1, x_2, \dots, x_p\$.
  
  Constraints
  
  
  \$1 \le s, p \le 50000\$
  \$−10^8 \le a_i \le b_i ≤ 10^8\$ for all \$0 \le i \lt s\$
  \$−10^8 \le x_j \le 10^8\$ for all \$0 \le j \lt p\$
  
  
  Output Format
  
  Output \$p\$ non-negative integers \$k_0, k_1, \dots , k_{p−1}\$ where \$k_i\$ is the number of segments which contain \$x_i\$.


My solution

For each point \$x_i\$ consider a pair (\$x_i, p\$). For each segment \$[a_i, b_i]\$ consider two pairs: (\$ai, 'l'\$) and (\$b_i, r\$) (\$p, l, r)\$ stand for point, left, and right, respectively).

Example: given three points \$x_1 = 5, x_2 = 8, x_3 = 3\$ and two segments \$[a_1, b_1] = [4, 10], [a_2,b_2] = [2, 6]\$. We then create the following list:

\$(5, p), (8, p), (3, p), (4, l), (10, r), (2, l), (6, r)\$

And then we sort it:

\$(2, l), (3, p), (4, l), (5, p), (6, r), (8, p), (10, r)\$

Now, let's scan it from left to right. The first item indicates the beginning of a segment (as it has l). The next is a point and we know that it is covered by one segment. The next item (4,l) indicates that we have the second segment. The next item (5,p) is a point and it is covered by two segments. The next item indicates the end of some segment, and so on.

import sys

def fast_count_segments(starts, ends, points):
    cnt = [0] * len(points)
    segments_num = 0

    listpoints = [(x, 'l') for x in starts]
    listpoints += [(x, 'p') for x in points]
    listpoints += [(x, 'r') for x in ends]

    listpoints.sort(key=lambda x: x[0], reverse=False)

    for p in listpoints:
        if p[1] == 'l':
            segments_num += 1
        elif p[1] == 'r':
            segments_num -= 1
        else:
            cnt[points.index(p[0])] = segments_num

    return cnt

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n = data[0]
    m = data[1]
    starts = data[2:2 * n + 2:2]
    ends   = data[3:2 * n + 2:2]
    points = data[2 * n + 2:]
    cnt = fast_count_segments(starts, ends, points)
    for x in cnt:
        print(x, end=' ')


Sample

Input:

2 3
0 5
7 10
1 6 11


Output:

1 0 0


For large input, my code run very slow, so I really need some reviews on my solution and my code to help reduce the runtime.
else:
    cnt[points.index(p[0])] = segments_num


Looking up the index of every point here is slow. A quick fix would be to store counts in a dict and traverse it in the correct order afterwards; see how that performs.

cnt = {}
segments_num = 0




else:
    cnt[p[0]] = segments_num




return [cnt[x] for x in points]


It also looks like your solution isn’t quite correct, since the sort could put lefts, rights, and points at the same location in different orders. Since the correct order of left, point, right also happens to be in alphabetical order, you can do another minimal fix and replace this:

listpoints.sort(key=lambda x: x[0], reverse=False)


with this:

listpoints.sort()


That’s a bit of a hack, but for this sort of task, it seems standard to keep the code short (fast to write in a competition?) rather than particularly expressive.