CF1168B.Good Triple

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Toad Rash has a binary string $s$ . A binary string consists only of zeros and ones.

Let $n$ be the length of $s$ .

Rash needs to find the number of such pairs of integers $l$ , $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$ , $k$ such that $1 \leq x, k \leq n$ , $l \leq x < x + 2k \leq r$ , and $s_x = s_{x+k} = s_{x+2k}$ .

Find this number of pairs for Rash.

输入格式

The first line contains the string $s$ ( $1 \leq |s| \leq 300\,000$ ), consisting of zeros and ones.

输出格式

Output one integer: the number of such pairs of integers $l$ , $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$ , $k$ such that $1 \leq x, k \leq n$ , $l \leq x < x + 2k \leq r$ , and $s_x = s_{x+k} = s_{x+2k}$ .

输入输出样例

输入#1
```
010101
```
输出#1
```
3
```
输入#2
```
11001100
```
输出#2
```
0
```

说明/提示

In the first example, there are three $l$ , $r$ pairs we need to count: $1$ , $6$ ; $2$ , $6$ ; and $1$ , $5$ .

In the second example, there are no values $x$ , $k$ for the initial string, so the answer is $0$ .

首页