E. Palindromic-quadruples

Codeforces

IDCF10105E

Time30000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Consider a numeric string str where stri denotes the digit(0 to 9) at index i. We call (x1, x2, x3, x4) quadruple a palindromic quadruple of string S if it satisfies the following criteria : Sx1 = Sx4 and Sx2 = Sx3 where x1 < x2 < x3 < x4. You are given Q queries where each query is of form : The first line contains a string str, such that , and . The second line contains a single integer, Q(1 ≤ Q ≤ 105), the number of queries. Each of the next Q lines contains a query, with format as described in the problem statement. In queries of type 2, . An integer for each query of type 1, one on each line. In the sample test case ## Input The first line contains a string str, such that , and . The second line contains a single integer, Q(1 ≤ Q ≤ 105), the number of queries. Each of the next Q lines contains a query, with format as described in the problem statement. In queries of type 2, . ## Output An integer for each query of type 1, one on each line. [samples] ## Note In the sample test case Query 1: The String is _01010_, Possible palindromic quadruples = _0110_, so answer = 1 Query 2: Update str2 = 0, so the string is now _00010_ Query 3: The String is _00010_, Possible palindromic quadruples = _0000_, so answer = 1 Query 4: Update str4 = 0, so the string is now _00000_ Query 5: The String is _00000_, Possible palindromic quadruples is _0000_ which can be selected in 5 ways, so answer = 5

**Definitions** Let $ S \in \{0,1,\dots,9\}^n $ be a numeric string of length $ n $. A quadruple $ (x_1, x_2, x_3, x_4) $ is *palindromic* if: $$ x_1 < x_2 < x_3 < x_4 \quad \text{and} \quad S[x_1] = S[x_4] \quad \text{and} \quad S[x_2] = S[x_3] $$ **Constraints** - $ 1 \leq n \leq 10^5 $ - $ 1 \leq Q \leq 10^5 $ **Operations** For each query: - Type 1: Given indices $ (x_1, x_2, x_3, x_4) $ with $ x_1 < x_2 < x_3 < x_4 $, output whether $ S[x_1] = S[x_4] $ and $ S[x_2] = S[x_3] $. - Type 2: Update $ S[i] \leftarrow d $ for some index $ i $ and digit $ d \in \{0,1,\dots,9\} $. **Objective** For each query of type 1, output $ 1 $ if the quadruple is palindromic, otherwise $ 0 $.

API Response (JSON)

{
  "problem": {
    "name": "E. Palindromic-quadruples",
    "description": {
      "content": "Consider a numeric string str where stri denotes the digit(0 to 9) at index i. We call (x1, x2, x3, x4) quadruple a palindromic quadruple of string S if it satisfies the following criteria : Sx1 = Sx4",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 30000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10105E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider a numeric string str where stri denotes the digit(0 to 9) at index i. We call (x1, x2, x3, x4) quadruple a palindromic quadruple of string S if it satisfies the following criteria : Sx1 = Sx4...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S \\in \\{0,1,\\dots,9\\}^n $ be a numeric string of length $ n $.  \nA quadruple $ (x_1, x_2, x_3, x_4) $ is *palindromic* if:  \n$$ x_1 < x_2 < x_3 < x_4 \\quad \\text{and} \\quad S[x...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments