G - Kadomatsu Subsequence Editorial by spheniscine Editorial for printing


Processing the values from left to right, let the current index processed be \(j\).

This index would only contribute to the answer if \(A_j\) is divisible by \(5\). We could then note that the matching \(A_i = x = {\large\frac{A_j}{5}} \cdot 7\) and \(A_k = y = {\large\frac{A_j}{5}} \cdot 3\). Since \(j\) must be the maximum or minimum indices among \(i, j, k\), the amount to add to the answer is \(c_{L}[x] \cdot c_L[y] + c_R[x] \cdot c_R[y]\), where \(c_L[x]\) represents the number of indices \(i < j\) where \(A_i = x\), while \(c_R[x]\) represents the number of indices \(i > j\) likewise.

Both \(c_L\) and \(c_R\) can be updated using associative arrays, thus this problem is solved in \(O(N \log N)\) or \(O(N)\) time, depending on the type of associative array used.

posted:
last update: