L. Queries on a String

Codeforces

IDCF10175L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A string s is given. Also there is a string p, and initially it is empty. You need to perform q operations of kind «add a letter to the end of the string p» and «remove a letter from the end of the string p», and after performing each operation you must say whether or not s contains p as a subsequence. The first line contains the string s of length from 1 to 200000, consisting of lowercase Latin letters. The second line contains a single integer q (1 ≤ q ≤ 200000) — the number of operations. Each of the next q lines describes an operation in the format «_push c_», which means «add letter c to the end of the string p» (c is lowercase Latin letter), or «_pop_», which means «remove letter from the end of the string p». The «_pop_» operations is guaranteed never to be applied to the empty string p. Output q lines, each of which equals «_YES_» or «_NO_», depending on whether or not the string p is contained in the string s as a subsequence after performing the corresponding operation. ## Input The first line contains the string s of length from 1 to 200000, consisting of lowercase Latin letters.The second line contains a single integer q (1 ≤ q ≤ 200000) — the number of operations.Each of the next q lines describes an operation in the format «_push c_», which means «add letter c to the end of the string p» (c is lowercase Latin letter), or «_pop_», which means «remove letter from the end of the string p». The «_pop_» operations is guaranteed never to be applied to the empty string p. ## Output Output q lines, each of which equals «_YES_» or «_NO_», depending on whether or not the string p is contained in the string s as a subsequence after performing the corresponding operation. [samples]

**Definitions** Let $ s \in \Sigma^* $ be a fixed string of length $ n $, where $ \Sigma $ is the set of lowercase Latin letters. Let $ p \in \Sigma^* $ be a dynamic string, initially empty. Let $ Q = (o_1, o_2, \dots, o_q) $ be a sequence of $ q $ operations, where each $ o_i \in \{ \texttt{push}(c), \texttt{pop} \} $, $ c \in \Sigma $. **Constraints** 1. $ 1 \leq |s| \leq 200000 $ 2. $ 1 \leq q \leq 200000 $ 3. Each `pop` operation is applied only when $ p \neq \varepsilon $. 4. All characters in $ s $ and operations are lowercase Latin letters. **Objective** After each operation $ o_i $, update $ p $ accordingly and determine whether $ p $ is a subsequence of $ s $. Output "YES" if $ p \sqsubseteq s $, otherwise "NO". Formally, for each $ i \in \{1, \dots, q\} $: - If $ o_i = \texttt{push}(c) $, then $ p \leftarrow p \cdot c $ - If $ o_i = \texttt{pop} $, then $ p \leftarrow p[1..|p|-1] $ Then output $ \texttt{YES} $ if $ p $ is a subsequence of $ s $, else $ \texttt{NO} $.

API Response (JSON)

{
  "problem": {
    "name": "L. Queries on a String",
    "description": {
      "content": "A string s is given. Also there is a string p, and initially it is empty. You need to perform q operations of kind «add a letter to the end of the string p» and «remove a letter from the end of the st",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10175L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string s is given. Also there is a string p, and initially it is empty. You need to perform q operations of kind «add a letter to the end of the string p» and «remove a letter from the end of the st...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be a fixed string of length $ n $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ p \\in \\Sigma^* $ be a dynamic string, initially empty.  \nLet...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments