A. The Monster

Codeforces

IDCF917A

Time1000ms

Memory256MB

Difficulty—

dpgreedyimplementationmath

English · Original

Chinese · Translation

Formal · Original

As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him. <center>![image](https://espresso.codeforces.com/33b71a2fd4e74aa2ac6ea032632c7ca223c838ba.png)</center>Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem. A string consisting only of parentheses ('_(_' and '_)_') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally: * Empty string is a correct bracket sequence. * if _s_ is a correct bracket sequence, then (_s_) is also a correct bracket sequence. * if _s_ and _t_ are correct bracket sequences, then _st_ (concatenation of _s_ and _t_) is also a correct bracket sequence. A string consisting of parentheses and question marks ('_?_') is called pretty if and only if there's a way to replace each question mark with either '_(_' or '_)_' such that the resulting string is a **non-empty** correct bracket sequence. Will gave his mom a string _s_ consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (_l_, _r_) such that 1 ≤ _l_ ≤ _r_ ≤ |_s_| and the string _s__l__s__l_ + 1... _s__r_ is pretty, where _s__i_ is _i_\-th character of _s_. Joyce doesn't know anything about bracket sequences, so she asked for your help. ## Input The first and only line of input contains string _s_, consisting only of characters '_(_', '_)_' and '_?_' (2 ≤ |_s_| ≤ 5000). ## Output Print the answer to Will's puzzle in the first and only line of output. [samples] ## Note For the first sample testcase, the pretty substrings of _s_ are: 1. "_(?_" which can be transformed to "_()_". 2. "_?)_" which can be transformed to "_()_". 3. "_((?)_" which can be transformed to "_(())_". 4. "_(?))_" which can be transformed to "_(())_". For the second sample testcase, the pretty substrings of _s_ are: 1. "_??_" which can be transformed to "_()_". 2. "_()_". 3. "_??()_" which can be transformed to "_()()_". 4. "_?()?_" which can be transformed to "_(())_". 5. "_??_" which can be transformed to "_()_". 6. "_()??_" which can be transformed to "_()()_". 7. "_??()??_" which can be transformed to "_()()()_".

由于Will被困在颠倒世界中，他仍然可以通过圣诞灯与母亲Joyce沟通（他可以用意念控制灯的开关）。但他无法直接告诉母亲自己的位置，因为抓走他的怪物会知道并重新定位他。因此，他想出了一个谜题来告诉母亲自己的坐标。他的坐标就是以下问题的答案：仅由括号（'(' 和 ')'）组成的字符串称为括号序列。某些括号序列被称为正确的括号序列。更正式地：一个由括号和问号（'?'）组成的字符串被称为“漂亮的”，当且仅当存在一种方式，将每个问号替换为 '(' 或 ')'，使得所得字符串是一个*非空*的正确括号序列。 Will通过灯光（摩斯电码）向母亲发送了一个由括号和问号组成的字符串 #cf_span[s]，他的坐标就是满足以下条件的整数对 #cf_span[(l, r)] 的数量：#cf_span[1 ≤ l ≤ r ≤ |s|]，且子串 #cf_span[slsl + 1... sr] 是漂亮的，其中 #cf_span[si] 表示 #cf_span[s] 的第 #cf_span[i] 个字符。 Joyce对括号序列一无所知，因此她向你寻求帮助。输入的第一行也是唯一一行包含字符串 #cf_span[s]，仅由字符 '('、')' 和 '?' 组成（#cf_span[2 ≤ |s| ≤ 5000]）。请在输出的第一行也是唯一一行输出Will谜题的答案。 ## Input 输入的第一行也是唯一一行包含字符串 #cf_span[s]，仅由字符 '('、')' 和 '?' 组成（#cf_span[2 ≤ |s| ≤ 5000]）。 ## Output 请在输出的第一行也是唯一一行输出Will谜题的答案。 [samples] ## Note 对于第一个测试用例，#cf_span[s] 的漂亮子串有： "_(?_" 可以转换为 "_()_"。 "_?)_" 可以转换为 "_()_"。 "_((?)_" 可以转换为 "_(())_"。 "_(?))_" 可以转换为 "_(())_"。对于第二个测试用例，#cf_span[s] 的漂亮子串有： "_??_" 可以转换为 "_()_"。 "_()_"。 "_??()_" 可以转换为 "_()()_"。 "_?()?_" 可以转换为 "_(())_"。 "_??_" 可以转换为 "_()_"。 "_()??_" 可以转换为 "_()()_"。 "_??()??_" 可以转换为 "_()()()_"。

**Definitions** Let $ s \in \{ \texttt{(}, \texttt{)}, \texttt{?} \}^n $ be a string of length $ n $, where $ 2 \leq n \leq 5000 $. A substring $ s[l:r] $ (with $ 1 \leq l \leq r \leq n $) is called *pretty* if there exists a replacement of each $ \texttt{?} $ with either $ \texttt{(} $ or $ \texttt{)} $ such that the resulting string is a non-empty correct bracket sequence. **Constraints** - $ 2 \leq |s| \leq 5000 $ - Each character of $ s $ is in $ \{ \texttt{(}, \texttt{)}, \texttt{?} \} $ **Objective** Compute the number of pairs $ (l, r) $ such that $ 1 \leq l \leq r \leq n $ and the substring $ s[l:r] $ is pretty.

Samples

Input #1

((?))

Output #1

Input #2

??()??

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. The Monster",
    "description": {
      "content": "As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is,",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF917A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is,...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "由于Will被困在颠倒世界中，他仍然可以通过圣诞灯与母亲Joyce沟通（他可以用意念控制灯的开关）。但他无法直接告诉母亲自己的位置，因为抓走他的怪物会知道并重新定位他。\n\n因此，他想出了一个谜题来告诉母亲自己的坐标。他的坐标就是以下问题的答案：\n\n仅由括号（'(' 和 ')'）组成的字符串称为括号序列。某些括号序列被称为正确的括号序列。更正式地：\n\n一个由括号和问号（'?'）组成的字符串被称为“漂...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{ \\texttt{(}, \\texttt{)}, \\texttt{?} \\}^n $ be a string of length $ n $, where $ 2 \\leq n \\leq 5000 $.  \nA substring $ s[l:r] $ (with $ 1 \\leq l \\leq r \\leq n $) is call...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments