Bedao Mini Contest 18 - BALANCE

Xem dạng PDF

Gửi bài giải


Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy số nguyên dương ~A~ có ~n~ phần tử. Hãy đếm số đoạn con liên tiếp, không rỗng và cân bằng của dãy. Được biết một đoạn ~[l, r]~ được coi là cân bằng nếu như ~O \ge E^2 + 7~ với ~O~ là số lượng số lẻ và ~E~ là số lượng số chẵn trong đoạn con đó.

Input

  • Dòng đầu tiên chứa số ~n~, độ dài của dãy số ~(1 \le n \le 3 \times 10^5)~

  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~

Output

  • Một số nguyên dương duy nhất là số đoạn con ~[l, r]~ cân bằng.

Subtask

  • ~20\%~ số test đầu có ~n \leq 1000~.

  • ~30\%~ số test khác thoả mãn ~n \le 10^5~.

  • ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

11
1 2 1 1 1 1 1 1 1 1 2

Sample Output 1

7

Note

  • Có ~7~ đoạn con cân bằng đó là ~[1, 9], [1, 10], [2, 10], [3, 9], [3, 10], [3, 11], [4, 10]~

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.