I. Another Query Problem

Codeforces

IDCF10241I

Time5000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Given the length $n$ of an array $A$ such that all $A_i$ $=$ $0$ for all $1 <= i <= n$. You need to answer $q$ queries of two types: 1) $1$ $l$ $r$ print 1 if all values of $A_i$, such that $l <= i <= r$, are equal. 2) $2$ $l$ $r$ $a$ $b$ update the range $l$ $r$ with the arithmetic progression $a + b * (i -l)$. For example if $l = 2$, $r = 5$, $a = 4$, and $b = 3$ then: $A_2 = A_2 + 4$ $A_3 = A_3 + 4 + 3$ $A_4 = A_4 + 4 + 2 * 3$ $A_5 = A_5 + 4 + 3 * 3$ First line contains two integers $n$ and $q$ $(1 <= n, q <= 2 * 10^5)$. Each of the next q lines follow one of two formates: 1) $1$ $l$ $r$ $(1 <= l <= r <= n)$ 2) $2$ $l$ $r$ $a$ $b$ $(-10^8 <= a, b <= 10^8)$ For each query of the second type print $1$ if the range is made up of the same value and $0$ if it's not. ## Input First line contains two integers $n$ and $q$ $(1 <= n, q <= 2 * 10^5)$.Each of the next q lines follow one of two formates:1) $1$ $l$ $r$ $(1 <= l <= r <= n)$2) $2$ $l$ $r$ $a$ $b$ $(-10^8 <= a, b <= 10^8)$ ## Output For each query of the second type print $1$ if the range is made up of the same value and $0$ if it's not. [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ with $ 1 \le n, q \le 2 \cdot 10^5 $. Let $ A = (A_1, A_2, \dots, A_n) $ be an array of integers initialized as $ A_i = 0 $ for all $ i \in \{1, \dots, n\} $. **Constraints** 1. For each query: - Type 1: $ 1 \le l \le r \le n $ - Type 2: $ 1 \le l \le r \le n $, $ -10^8 \le a, b \le 10^8 $ **Operations** For a query of type $ 1\ l\ r $: Output $ 1 $ if $ \forall i,j \in [l, r],\ A_i = A_j $; otherwise output $ 0 $. For a query of type $ 2\ l\ r\ a\ b $: For each $ i \in [l, r] $, update: $$ A_i \gets A_i + a + b \cdot (i - l) $$ **Objective** For each query of type 1, output $ \mathbb{I}\left( \forall i,j \in [l,r],\ A_i = A_j \right) $, where $ \mathbb{I} $ is the indicator function.

API Response (JSON)

{
  "problem": {
    "name": "I. Another Query Problem",
    "description": {
      "content": "Given the length $n$ of an array $A$ such that all $A_i$ $=$ $0$ for all $1 <= i <= n$. You need to answer $q$ queries of two types: 1) $1$ $l$ $r$ print 1 if all values of $A_i$, such that $l <= i ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10241I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given the length $n$ of an array $A$ such that all $A_i$ $=$ $0$ for all $1 <= i <= n$.\n\nYou need to answer $q$ queries of two types:\n\n1) $1$ $l$ $r$ print 1 if all values of $A_i$, such that $l <= i ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ with $ 1 \\le n, q \\le 2 \\cdot 10^5 $.  \nLet $ A = (A_1, A_2, \\dots, A_n) $ be an array of integers initialized as $ A_i = 0 $ for all $ i \\in \\{1, \\dots...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments