CCC '22 S4 - Good Triplets - DMOJ: Modern Online Judge

CCC '22 S4 - Good Triplets

Points: 15 (partial)

Time limit: 3.0s

Memory limit: 1G

Author:

Problem types

Canadian Computing Competition: 2022 Stage 1, Senior #4

Andrew is a very curious student who drew a circle with the center at $(0, 0)$ ~(0, 0)~ and an integer circumference of $C \ge 3$ ~C \ge 3~. The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.

$\text{[math]}$

Andrew drew $N \ge 3$ ~N \ge 3~ points at integer locations. In particular, the $i^\text{th}$ ~i^\text{th}~ point is drawn at location $P_i$ ~P_i~ $(0 \le P_i \le C-1)$ ~(0 \le P_i \le C-1)~. It is possible for Andrew to draw multiple points at the same location.

A good triplet is defined as a triplet $(a, b, c)$ ~(a, b, c)~ that satisfies the following conditions:

$1 \le a < b < c \le N$ ~1 \le a < b < c \le N~.
The origin $(0, 0)$ ~(0, 0)~ lies strictly inside the triangle with vertices at $P_a$ ~P_a~, $P_b$ ~P_b~, and $P_c$ ~P_c~. In particular, the origin is not on the triangle's perimeter.

Lastly, two triplets $(a, b, c)$ ~(a, b, c)~ and $(a', b', c')$ ~(a', b', c')~ are distinct if $a \ne a'$ ~a \ne a'~, $b \ne b'$ ~b \ne b'~, or $c \ne c'$ ~c \ne c'~.

Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.

Input Specification

The first line contains the integers $N$ ~N~ and $C$ ~C~, separated by one space.

The second line contains $N$ ~N~ space-separated integers. The $i^\text{th}$ ~i^\text{th}~ integer is $P_i$ ~P_i~ $(0 \le P_i \le C-1)$ ~(0 \le P_i \le C-1)~.

The following table shows how the available 15 marks are distributed.

Marks Awarded	Number of Points	Circumference	Additional Constraints
$3$ ~3~ marks	$3 \le N \le 200$ ~3 \le N \le 200~	$3 \le C \le 10^6$ ~3 \le C \le 10^6~	None
$3$ ~3~ marks	$3 \le N \le 10^6$ ~3 \le N \le 10^6~	$3 \le C \le 6\,000$ ~3 \le C \le 6\,000~	None
$6$ ~6~ marks	$3 \le N \le 10^6$ ~3 \le N \le 10^6~	$3 \le C \le 10^6$ ~3 \le C \le 10^6~	$P_1, P_2, \dots, P_N$ ~P_1, P_2, \dots, P_N~ are all distinct (i.e., every location contains at most one point)
$3$ ~3~ marks	$3 \le N \le 10^6$ ~3 \le N \le 10^6~	$3 \le C \le 10^6$ ~3 \le C \le 10^6~	None

Output Specification

Output the number of distinct good triplets.

Sample Input

8 10
0 2 5 5 6 9 0 0

Output for Sample Input

Explanation of Output for Sample Input

Andrew drew the following diagram.

$\text{[math]}$

The origin lies strictly inside the triangle with vertices $P_1$ ~P_1~, $P_2$ ~P_2~, and $P_5$ ~P_5~, so $(1, 2, 5)$ ~(1, 2, 5)~ is a good triplet. The other five good triplets are $(2, 3, 6)$ ~(2, 3, 6)~, $(2, 4, 6)$ ~(2, 4, 6)~, $(2, 5, 6)$ ~(2, 5, 6)~, $(2, 5, 7)$ ~(2, 5, 7)~, and $(2, 5, 8)$ ~(2, 5, 8)~.

Comments

There are no comments at the moment.