L. Expression Queries

Codeforces

IDCF730L

Time4000ms

Memory512MB

Difficulty—

data structures

English · Original

Chinese · Translation

Formal · Original

A _simplified arithmetic expression_ (SAE) is an arithmetic expression defined by the following grammar: * _<SAE> ::= <Number> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)_ * _<Number> ::= <Digit> | <Digit><Number>_ * _<Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9_ In other words it's a correct arithmetic expression that is allowed to contain brackets, numbers (possibly with leading zeros), multiplications and additions. For example expressions "_(0+01)_", "_0_" and "_1*(0)_" are simplified arithmetic expressions, but expressions "_2-1_", "_+1_" and "_1+2)_" are not. Given a string _s_1_s_2..._s_|_s_| that represents a SAE; _s__i_ denotes the _i_\-th character of the string which can be either a digit ('_0_'-'_9_'), a plus sign ('_+_'), a multiplication sign ('_*_'), an opening round bracket '_(_' or a closing round bracket '_)_'. A part _s__l__s__l_ + 1..._s__r_ of this string is called a _sub-expression_ if and only if it is a SAE. You task is to answer _m_ queries, each of which is a pair of integers _l__i_, _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ |_s_|). For each query determine whether the corresponding part of the given string is a sub-expression and in case it's a sub-expression calculate its value modulo 1000000007 (109 + 7). The values should be calculated using standard operator priorities. ## Input The first line of the input contains non-empty string _s_ (1 ≤ |_s_| ≤ 4·105) which represents a correct SAE. Each character of the string can be one of the following characters: '_*_', '_+_', '_(_', '_)_' or a digit ('_0_'-'_9_'). The expression might contain extra-huge numbers. The second line contains an integer _m_ (1 ≤ _m_ ≤ 4·105) which is the number of queries. Each of the next _m_ lines contains two space-separated integers _l__i_, _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ |_s_|) — the _i_\-th query. ## Output The _i_\-th number of output should be the answer for the _i_\-th query. If the _i_\-th query corresponds to a valid sub-expression output the value of the sub-expression modulo 1000000007 (109 + 7). Otherwise output -1 as an answer for the query. Print numbers on separate lines. [samples]

一个_简化算术表达式_（SAE）是由以下文法定义的算术表达式：换句话说，它是一个合法的算术表达式，允许包含括号、数字（可能带有前导零）、乘法和加法。例如，表达式 "_(0+01)_"、"_0_" 和 "_1*(0)_" 是简化算术表达式，但表达式 "_2-1_"、"_+1_" 和 "_1+2)_" 不是。给定一个表示 SAE 的字符串 #cf_span[s1s2...s|s|]；#cf_span[si] 表示字符串的第 #cf_span[i] 个字符，它可以是数字（'_0_'-'_9_'）、加号（'_+_'）、乘号（'*'）、左括号 '_(_' 或右括号 '_)_'。该字符串的子串 #cf_span[slsl + 1...sr] 被称为一个_子表达式_，当且仅当它是一个 SAE。你的任务是回答 #cf_span[m] 个查询，每个查询是一对整数 #cf_span[li], #cf_span[ri] #cf_span[(1 ≤ li ≤ ri ≤ |s|)]。对于每个查询，判断给定字符串的对应部分是否为子表达式；如果是子表达式，则计算其值对 #cf_span[1000000007 (109 + 7)] 取模的结果。计算值时应使用标准运算符优先级。输入的第一行包含一个非空字符串 #cf_span[s] #cf_span[(1 ≤ |s| ≤ 4·105)]，表示一个合法的 SAE。字符串中的每个字符可以是以下字符之一：'_*_', '_+_', '_(_', '_)_' 或数字（'_0_'-'_9_'）。表达式可能包含超大数字。第二行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 4·105)]，表示查询的数量。接下来的 #cf_span[m] 行每行包含两个用空格分隔的整数 #cf_span[li], #cf_span[ri] #cf_span[(1 ≤ li ≤ ri ≤ |s|)] —— 第 #cf_span[i] 个查询。输出的第 #cf_span[i] 个数应为第 #cf_span[i] 个查询的答案。如果第 #cf_span[i] 个查询对应一个有效的子表达式，则输出该子表达式的值对 #cf_span[1000000007 (109 + 7)] 取模的结果；否则输出 -1。每行输出一个数字。 ## Input 输入的第一行包含一个非空字符串 #cf_span[s] #cf_span[(1 ≤ |s| ≤ 4·105)]，表示一个合法的 SAE。字符串中的每个字符可以是以下字符之一：'_*_', '_+_', '_(_', '_)_' 或数字（'_0_'-'_9_'）。表达式可能包含超大数字。第二行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 4·105)]，表示查询的数量。接下来的 #cf_span[m] 行每行包含两个用空格分隔的整数 #cf_span[li], #cf_span[ri] #cf_span[(1 ≤ li ≤ ri ≤ |s|)] —— 第 #cf_span[i] 个查询。 ## Output 输出的第 #cf_span[i] 个数应为第 #cf_span[i] 个查询的答案。如果第 #cf_span[i] 个查询对应一个有效的子表达式，则输出该子表达式的值对 #cf_span[1000000007 (109 + 7)] 取模的结果；否则输出 -1。每行输出一个数字。 [samples]

**Definitions** Let $ s \in \{ \text{digits}, +, *, (, ) \}^* $ be a string representing a valid Simplified Arithmetic Expression (SAE). Let $ \mathcal{L} $ be the language of SAEs defined by the grammar: - $ \text{expr} \to \text{term} \; (\texttt{+} \; \text{term})* $ - $ \text{term} \to \text{factor} \; (\texttt{*} \; \text{factor})* $ - $ \text{factor} \to \text{number} \; | \; \texttt{(} \; \text{expr} \; \texttt{)} $ - $ \text{number} \to \text{digit}^+ $ - $ \text{digit} \in \{ \texttt{0}, \dots, \texttt{9} \} $ A substring $ s[l:r] $ is a *sub-expression* if and only if $ s[l:r] \in \mathcal{L} $. **Constraints** 1. $ 1 \le |s| \le 4 \cdot 10^5 $ 2. $ 1 \le m \le 4 \cdot 10^5 $ 3. For each query $ (l_i, r_i) $: $ 1 \le l_i \le r_i \le |s| $ **Objective** For each query $ (l_i, r_i) $: - If $ s[l_i:r_i] \in \mathcal{L} $, compute $ v_i = \text{eval}(s[l_i:r_i]) \mod 1000000007 $ - Otherwise, output $ -1 $ Output $ m $ lines, each containing $ v_i $ or $ -1 $.

Samples

Input #1

((1+2)*3+101*2)
6
8 14
1 6
2 10
11 14
5 5
4 5

Output #1

Input #2

(01)
1
1 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "L. Expression Queries",
    "description": {
      "content": "A _simplified arithmetic expression_ (SAE) is an arithmetic expression defined by the following grammar: *   _<SAE> ::= <Number> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)_ *   _<Number> ::= <Digit> | <Di",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF730L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A _simplified arithmetic expression_ (SAE) is an arithmetic expression defined by the following grammar:\n\n*   _<SAE> ::= <Number> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)_\n*   _<Number> ::= <Digit> | <Di...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一个_简化算术表达式_（SAE）是由以下文法定义的算术表达式：\n\n换句话说，它是一个合法的算术表达式，允许包含括号、数字（可能带有前导零）、乘法和加法。例如，表达式 \"_(0+01)_\"、\"_0_\" 和 \"_1*(0)_\" 是简化算术表达式，但表达式 \"_2-1_\"、\"_+1_\" 和 \"_1+2)_\" 不是。\n\n给定一个表示 SAE 的字符串 #cf_span[s1s2...s|s|]；#cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{ \\text{digits}, +, *, (, ) \\}^* $ be a string representing a valid Simplified Arithmetic Expression (SAE).  \nLet $ \\mathcal{L} $ be the language of SAEs defined by the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments