737 . 碉堡防禦

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

asuka
酸欠少女

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

58.8% (10/17)

Tags

apcsc apcsc-dc

Description

在一座戒備森嚴的碉堡中，有 $N$ 組每組 $2$ 人的士兵在守衛，其中第 $i$ 組士兵能力值排名第 $i$。碉堡的兩邊都有可能被攻擊，因此理想狀況下，一個穩定的碉堡防禦應該讓能力最強的人在內側，也就是排成 $N, N-1, \dots, 2, 1, 1, 2, \dots, N-1, N$。

根據這個理論，將軍把每個士兵的穩定值定義為有多少組排名比自己大的士兵兩人在自己的異側，而碉堡防禦值為所有士兵的穩定值總和。例如：三組士兵排成 $1, 3, 2, 3, 1, 2$，他們穩定值分別為 $0, 0, 1, 0, 1, 0$，因此雕堡防禦值為 $2$。

現在給一個士兵的排列，請你回答碉堡防禦值為和？

Input Format

輸入第一行是一個整數 $N$，表示有多少組士兵。

輸入第二行是 $2N$ 個以空白分隔的整數 $a_i$，依序代表整排士兵的能力值排名。

輸入保證 $1\le a_i\le N$，且每個數字恰出現兩次。

對於 $20\%$ 的測資，保證 $N\le 1000$。
對於剩下 $40\%$ 的測資，保證 $N\le 40000$。
對於剩下 $40\%$ 的測資，保證 $N\le 100000$。

Output Format

輸出一行一個整數代表雕堡防禦值。

Sample Input 1

3
1 3 2 3 1 2

Sample Output 1

2

Sample Input 2

4
3 2 4 4 1 1 2 3

Sample Output 2

6

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~10 $1\le N\le 100$ 20
3 0~16 $1\le N \le 40000$ 40
4 0~23 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4
1 2000 524288 65536 1 2 3 4
2 2000 524288 65536 2 3 4
3 2000 524288 65536 2 3 4
4 2000 524288 65536 2 3 4
5 2000 524288 65536 2 3 4
6 2000 524288 65536 2 3 4
7 2000 524288 65536 2 3 4
8 2000 524288 65536 2 3 4
9 2000 524288 65536 2 3 4
10 2000 524288 65536 2 3 4
11 2000 524288 65536 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 3 4
14 2000 524288 65536 3 4
15 2000 524288 65536 3 4
16 2000 524288 65536 3 4
17 2000 524288 65536 4
18 2000 524288 65536 4
19 2000 524288 65536 4
20 2000 524288 65536 4
21 2000 524288 65536 4
22 2000 524288 65536 4
23 2000 524288 65536 4
Submit
Back to Top