DMOPC '20 Contest 3 P2 - Bob and Parallel-Ks

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Bob is composing a song for M singers to perform! The song lasts for N beats, and the x-th singer is assigned a series of N notes a_{x, 1}, \ldots, a_{x, N} to sing on each of the beats. Notes are represented by integer values, and the M notes sung on a single beat are all distinct.

Unfortunately, Bob needs to watch out for parallel-Ks. A parallel-K is a triple (x, y, t) such that a_{y, t} - a_{x, t} = a_{y, t + 1} - a_{x,t + 1} = K. In other words, a parallel-K is two singers x and y, plus a beat t, such that the notes that x and y sing form an interval of K on both beats t and t + 1.

Parallel-Ks make music sound absolutely horrendous (for some reason), so please help Bob find all the parallel-Ks in his song!

Constraints

1 \le N \le 20
1 \le K \le 10^9
1 \le a_{ij} \le 10^9
For a given j, a_{1j}, \ldots, a_{Mj} are distinct.

Subtask 1 [2/15]

1 \le M \le 1\,000

Subtask 2 [5/15]

1 \le M \le 50\,000

Subtask 3 [8/15]

1 \le M \le 200\,000

Input Specification

The first line contains three space-separated integers: M, N, and K.
The next M lines each contain N space-separated integers, a_{i1}, \ldots, a_{iN}, the notes sung on each beat by singer i.

Output Specification

The number of distinct parallel-Ks in Bob's song. (Two parallel-Ks (x_1, y_1, t_1) and (x_2, y_2, t_2) are distinct if x_1 \neq x_2, or y_1 \neq y_2, or t_1 \neq t_2.)

Sample Input

5 3 5
5 6 6
10 11 11
15 16 16
105 116 118
110 111 113

Sample Output

5

Explanation for Sample Output

Singers 1 and 2 form two parallel-5s: one between beats 1 and 2, and another between beats 2 and 3. Singers 2 and 3 also form two parallel-5s. Finally, singers 5 and 4 form one parallel-5 between beats 2 and 3. In total, there are five parallel-5s: (1, 2, 1), (1, 2, 2), (2, 3, 1), (2, 3, 2), and (5, 4, 2). (Note that (4, 5, 2), (5, 4, 1), and (4, 5, 1) do not fit the definition of a parallel-5.)


Comments

There are no comments at the moment.