C - Swappable
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の整数からなる配列 A=(A_1,A_2,...,A_N) が与えられるので、次の条件を全て満たす整数組 (i,j) の数を求めてください。
- 1 \le i < j \le N
- A_i \neq A_j
制約
- 入力は全て整数
- 2 \le N \le 3 \times 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
3 1 7 1
出力例 1
2
この入力では、A=(1,7,1) です。
- 整数組 (1,2) に対して、A_1 \neq A_2 です。
- 整数組 (1,3) に対して、A_1 = A_3 です。
- 整数組 (2,3) に対して、A_2 \neq A_3 です。
入力例 2
10 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
出力例 2
45
入力例 3
20 7 8 1 1 4 9 9 6 8 2 4 1 1 9 5 5 5 3 6 4
出力例 3
173
Score : 300 points
Problem Statement
Given an array of N integers A=(A_1,A_2,...,A_N), find the number of pairs (i,j) of integers satisfying all of the following conditions:
- 1 \le i < j \le N
- A_i \neq A_j
Constraints
- All values in input are integers.
- 2 \le N \le 3 \times 10^5
- 1 \le A_i \le 10^9
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
3 1 7 1
Sample Output 1
2
In this input, we have A=(1,7,1).
- For the pair (1,2), A_1 \neq A_2.
- For the pair (1,3), A_1 = A_3.
- For the pair (2,3), A_2 \neq A_3.
Sample Input 2
10 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
Sample Output 2
45
Sample Input 3
20 7 8 1 1 4 9 9 6 8 2 4 1 1 9 5 5 5 3 6 4
Sample Output 3
173