D - Kadomatsu Subsequence 解説 by spheniscine


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.

投稿日時:
最終更新: