TopCoder

$\huge 南ことり$
$ε=ε=ε=(~ ̄▽ ̄)~烙跑囉$

User's AC Ratio

76.2% (16/21)

Submission's AC Ratio

30.4% (56/184)

Tags

Description

給一個數列,問有多少數對$(i,j)$滿足$ a_i \oplus a_{j} \geq max(a_i, a_{i+1}, \dots, a_j) \land i < j$ 。
其中$\oplus$是bitwise xor。

Input Format

第一行是一個正整數$n$
第二行有$n$個非負整數,代表數列
輸入之整數皆不大於$10^ 7$

Output Format

輸出一個整數代表答案

Sample Input 1

5
1 2 5 3 4

Sample Output 1

6

Hints

本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組19分(subtask 0~4),$N\leq 5\times 10^ 3$
第二組30分(subtask 5~6),$N\leq 3\times 10^ 5$
第三組51分(subtask 7~10),$N\leq 3\times 10^ 5$

Problem Source

tangent

Subtasks

No. Testdata Range Score
1 0~4 19
2 5~6 30
3 7~10 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 10000 262144 262144 2
6 10000 262144 262144 2
7 2000 262144 262144 3
8 2000 262144 262144 3
9 2000 262144 262144 3
10 2000 262144 262144 3