Tèo và xâu đối xứng (Bản không dễ)

Points: 100.00 (partial)

Time limit: 2.0s

Memory limit: 256M

Input: stdin

Output: stdout

Authors:

Lamle, UltimateWiener

Problem source:

swishy's kitchen

Problem type

Lưu ý: Bản không dễ và bản dễ chỉ khác nhau bởi giới hạn $n$ và điệu kiện của cặp $(l, r)$

Trong giờ học, Tèo được biết đến tới khái niệm xâu đối xứng. Một xâu đối xứng là một xâu khi đọc từ trái qua phải hay ngược lại đều như nhau. Nhưng vì định nghĩa quá nhàn đối với anh, Tèo quyết định sẽ xào nấu thêm một chút. Tèo định nghĩa một xâu $t$ là đẹp nếu $t$ là một xâu đối xứng và biểu diễn số của t chia hết cho 2, chia hết cho 3 và chia hết cho 5.

Ví dụ các xâu đẹp: $01233210, 030, 0000$ (Có thể có các chữ số $0$ thừa ở đầu xâu)

Cho một xâu kí tự $s$ gồm các chữ số $0$ đến $9$ . Hãy giúp tèo đếm có bao nhiêu cặp $(l, r)$ $(l \leq r)$ sao cho xâu $s_{l} s_{l + 1} . . . s_{r}$ đẹp và có độ dài lẻ. Sau một hồi suy nghĩ thì Tèo nghĩ mình có thể nấu quá cháy nên không tìm được cách giải. Vì thế, anh nhờ bạn giải giúp bài toán siêu khó của Tèo này.

Input

Gồm một dòng duy nhất chứa xâu kí tự $s$ $(| s | \leq 2 \cdot 10^{5})$ .

Output

In ra kết quả của bài toán.

Sample Input

Copy

Sample Output

Copy

Note

Các cặp $(l, r)$ thỏa mãn là $(1, 1)$ , $(3, 3)$ , $(1, 3)$ . Vì vậy, đáp án là $3$ .

Comments

Please read the guidelines before commenting.

-1

UltimateWiener commented 1:18:32 pm, 03/02/2025

Đã thêm 10 test mới siêu khó đoán

2

anhtuan2007 commented 10:37:01 am, 02/02/2025

test dễ đoán, mong ad tăng độ mạnh của test ạ:)