Contest Duration: - (local time) (100 minutes) Back to Home
Official

## D - Distinct Trio Editorial by en_translator

The condition can be rephrased as follows: “find the number of triplets $$(i,j,k)$$ such that $$A_i < A_j < A_k$$.”

details For a triplet $(i,j,k)$ satisfying the original condition, there exists a unique permutation of $i,j,k$ such that $A_i \lt A_j \lt A_k$. Conversely, for a triplet $(i,j,k)$ such that $A_i\lt A_j\lt A_k$, there exists a unique permutation of $i,j,k$ such that $i\lt j\lt k$.

Consider exhaustively enumerating $$j$$. Then, $$i$$ and $$k$$ can be chosen independently. The number of choices for $$i$$ is the number of elements of $$A$$ with values smaller than $$A_j$$, and the number of choices for $$k$$ is the number of elements of $$A$$ with values larger than $$A$$. Therefore, this problem can be solved in a total of $$O(N+\max A)$$ time by preparing an array of “how many elements of $$A$$ is less than $$x$$?”.

Sample code (Python)

posted:
last update: