DMOPC '20 Contest 2 P5 - Majority Subarrays

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.2s
Memory limit: 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are given an array of N positive integers a_1, a_2, \dots, a_N. Find the number of subarrays that have a majority element.

A subarray of length l has a majority element if some number appears strictly greater than \frac{1}{2}l times in the subarray.

Constraints

1 \le a_i \le N for all i.

Subtask 1 [5%]

1 \le N \le 100

Subtask 2 [10%]

1 \le N \le 500

Subtask 3 [15%]

1 \le N \le 2\,000

Subtask 4 [20%]

1 \le N \le 10\,000

Subtask 5 [25%]

1 \le N \le 100\,000

Subtask 6 [25%]

1 \le N \le 2\,000\,000

Input Specification

The first line of input contains one integer: N.

The second line of input contains N space-separated integers. The ith of these integers is a_i.

Output Specification

Output one number: the number of subarrays that have a majority element.

Sample Input 1

4
1 2 1 3

Sample Output 1

5

Explanation for Sample Input 1

All 4 single-element subarrays have a majority element, and the subarray [1,2,1] also has a majority element.

Sample Input 2

10
1 3 2 3 1 3 3 2 2 4

Sample Output 2

25

Comments

There are no comments at the moment.