C. The Monster

Codeforces

IDCF918C

Time1000ms

Memory256MB

Difficulty—

data structuresdpgreedyimplementationmath

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 "_()()()_".

[{"iden":"statement","content":"由于 Will 被困在颠倒世界中，他仍能通过圣诞灯与母亲 Joyce 通信（他可以用意念控制灯的开关）。但他无法直接告诉母亲自己的位置，因为将他掳至颠倒世界的怪物会得知并转移他。\n\n因此，他设计了一个谜题来告知母亲自己的坐标。他的坐标是以下问题的答案：\n\n仅由括号（'(' 和 ')'）组成的字符串称为括号序列。某些括号序列被称为正确的括号序列。更正式地：\n\n一个由括号和问号（'?'）组成的字符串，如果存在一种将每个问号替换为 '(' 或 ')' 的方式，使得结果字符串是一个*非空*的正确括号序列，则称该字符串为“优美的”。\n\nWill 通过灯光（摩斯电码）向母亲发送了一个由括号和问号组成的字符串 #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] 个字符。\n\nJoyce 对括号序列一无所知，因此她向你寻求帮助。\n\n输入的第一行也是唯一一行包含字符串 #cf_span[s]，仅由字符 '('、')' 和 '?' 组成（#cf_span[2 ≤ |s| ≤ 5000]）。\n\n请在输出的第一行也是唯一一行输出 Will 的谜题的答案。\n\n对于第一个样例测试用例，#cf_span[s] 的优美子串有：\n\n对于第二个样例测试用例，#cf_span[s] 的优美子串有：\n\n"},{"iden":"input","content":"输入的第一行也是唯一一行包含字符串 #cf_span[s]，仅由字符 '('、')' 和 '?' 组成（#cf_span[2 ≤ |s| ≤ 5000]）。"},{"iden":"output","content":"请在输出的第一行也是唯一一行输出 Will 的谜题的答案。"},{"iden":"examples","content":"输入\n((?))\n输出\n4\n输入\n??()??\n输出\n7"},{"iden":"note","content":"对于第一个样例测试用例，#cf_span[s] 的优美子串有：\n\"_(?_\" 可以变为 \"_()_\"。\n\"_?)_\" 可以变为 \"_()_\"。\n\"_((?)_\" 可以变为 \"_(())_\"。\n\"_(?))_\" 可以变为 \"_(())_\"。\n\n对于第二个样例测试用例，#cf_span[s] 的优美子串有：\n\"_??_\" 可以变为 \"_()_\"。\n\"_()_\"。\n\"_??()_\" 可以变为 \"_()()_\"。\n\"_?()?_\" 可以变为 \"_(())_\"。\n\"_??_\" 可以变为 \"_()_\"。\n\"_()??_\" 可以变为 \"_()()_\"。\n\"_??()??_\" 可以变为 \"_()()()_\"。 "}]}

Let $ s $ be a string of length $ n $, where each character is either '(', ')', or '?'. A substring $ s[l..r] $ (with $ 1 \leq l \leq r \leq n $) is called *pretty* if there exists a way to replace each '?' in $ s[l..r] $ with either '(' or ')' such that the resulting string is a **non-empty correct bracket sequence**. Define a correct bracket sequence as a string of parentheses that is balanced (equal number of opening and closing brackets, and at no prefix does the number of closing brackets exceed the number of opening brackets). Let $ f(l, r) = 1 $ if substring $ s[l..r] $ is pretty, and $ 0 $ otherwise. The goal is to compute: $$ \sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) $$

Samples

Input #1

((?))

Output #1

Input #2

??()??

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. 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": "CF918C"
  },
  "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": "[{\"iden\":\"statement\",\"content\":\"由于 Will 被困在颠倒世界中，他仍能通过圣诞灯与母亲 Joyce 通信（他可以用意念控制灯的开关）。但他无法直接告诉母亲自己的位置，因为将他掳至颠倒世界的怪物会得知并转移他。\\n\\n因此，他设计了一个谜题来告知母亲自己的坐标。他的坐标是以下问题的答案：\\n\\n仅由括号（'(' 和 ')'）组成的字符串称为括号序列。某些括号序列被称...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s $ be a string of length $ n $, where each character is either '(', ')', or '?'.\n\nA substring $ s[l..r] $ (with $ 1 \\leq l \\leq r \\leq n $) is called *pretty* if there exists a way to replace e...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments