{"problem":{"name":"M. Скобочная последовательность","description":{"content":"Назовём скобочную последовательность _идеальной_, если она образована некоторым количеством открывающих скобок, за которыми следует такое же количество закрывающих скобок. Глубиной идеальной скобочной","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10085M"},"statements":[{"statement_type":"Markdown","content":"Назовём скобочную последовательность _идеальной_, если она образована некоторым количеством открывающих скобок, за которыми следует такое же количество закрывающих скобок. Глубиной идеальной скобочной последовательности назовём количество скобок какого-то одного вида в ней. Глубиной скобки назовём количество скобок того же вида, включая её саму, до ближайшего к ней края последовательности. Например, последовательность _(((())))_ имеет глубину 4, а скобки в ней имеют глубины 1, 2, 3, 4, 4, 3, 2 и 1 соответственно.\n\nОчевидно, что любую скобочную последовательность можно преобразовать в идеальную (возможно, пустую), если удалить из неё некоторое количество скобок.\n\nВам дана скобочная последовательность, возможно, неидеальная. Для каждой скобки в этой последовательности требуется определить две величины:\n\nЕсли какая-то скобка не входит ни в какую идеальную скобочную последовательность, которую можно было бы получить удалением некоторых скобок из исходной последовательности, обе величины будем считать равными 0.\n\nВ единственной строке записана скобочная последовательность s, состоящая только из открывающих и закрывающих скобок. Ее длина length(s) находится в пределах от 1 до 105.\n\nВ первой строке выведите length(s) чисел — ответы на первый вопрос задачи для каждой скобки.\n\nВо второй строке выведите length(s) чисел — ответы на второй вопрос задачи для каждой скобки.\n\n## Входные Данные\n\nВ единственной строке записана скобочная последовательность s, состоящая только из открывающих и закрывающих скобок. Ее длина length(s) находится в пределах от 1 до 105.\n\n## Выходные Данные\n\nВ первой строке выведите length(s) чисел — ответы на первый вопрос задачи для каждой скобки.Во второй строке выведите length(s) чисел — ответы на второй вопрос задачи для каждой скобки.\n\n## Примеры\n\nВходные данные(()())Выходные данные1 2 2 2 2 12 2 2 2 2 2Входные данные))()(()(())())()((Выходные данные0 0 1 1 2 3 3 4 5 5 4 3 3 2 1 1 0 00 0 5 1 5 5 3 5 5 5 5 3 5 5 1 5 0 0\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s = s_1 s_2 \\dots s_n $ be a bracket sequence of length $ n $, where each $ s_i \\in \\{ \\texttt{(}, \\texttt{)} \\} $.  \n\nFor a bracket $ s_i $, define:  \n- **Ideal subsequence**: A subsequence of $ s $ of the form $ \\texttt{(}^k \\texttt{)}^k $ for some $ k \\geq 0 $, obtained by deleting some brackets.  \n- **Belongs to an ideal subsequence**: A bracket $ s_i $ is said to belong to *some* ideal subsequence if there exists an ideal subsequence containing $ s_i $.  \n- **Depth of a bracket** $ s_i $: If $ s_i $ belongs to some ideal subsequence, then its depth is the number of matching brackets in that ideal subsequence from $ s_i $ to the nearest end of the subsequence (i.e., the position index within the ideal subsequence’s nesting level).  \n- **Ideal depth of $ s_i $**: The maximum possible depth of $ s_i $ over *all* ideal subsequences containing it.  \n- **Maximum nesting depth of $ s_i $**: The maximum depth of the ideal subsequence that contains $ s_i $, i.e., the total number of opening brackets in such an ideal subsequence.  \n\nIf $ s_i $ does not belong to *any* ideal subsequence, both values are 0.\n\n**Constraints**  \n- $ 1 \\leq n \\leq 10^5 $  \n- $ s_i \\in \\{ \\texttt{(}, \\texttt{)} \\} $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFor each position $ i \\in \\{1, \\dots, n\\} $:  \n1. Compute $ d_i $: the **ideal depth** of $ s_i $ (maximum nesting level it can achieve in any ideal subsequence containing it), or 0 if it belongs to none.  \n2. Compute $ D_i $: the **maximum nesting depth** of the ideal subsequence containing $ s_i $ (i.e., the total number of opening brackets in such a subsequence), or 0 if it belongs to none.  \n\nOutput two lines:  \n- First line: $ d_1, d_2, \\dots, d_n $  \n- Second line: $ D_1, D_2, \\dots, D_n $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10085M","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}