A. Zero Array

Codeforces

IDCF10185A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow: A zero array is defined as an array which all its elements are zeros. There is only one allowed operation to convert an array to a zero array. At each operation, you can choose a value x and subtract it from all non-zero elements in the array, such that no element will be negative after the operation. The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases. The first line of each test case consists of two integers n and q (1 ≤ n, q ≤ 105), in which n is the size of the array a, and q is the number of queries. Then a line follows containing n elements a1, a2, ..., an (0 ≤ ai ≤ 109), giving the array a. Then q lines follow, each line containing a query in the format described in the problem statement. It is guaranteed that the following constraints hold for the first type of queries: 1 ≤ p ≤ n, 0 ≤ v ≤ 109. The sum of n and q overall test cases does not exceed 106 for each. For each query of the second type, print the minimum number of required operations to convert array a to a zero array. The queries must be answered in the order given in the input. ## Input The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.The first line of each test case consists of two integers n and q (1 ≤ n, q ≤ 105), in which n is the size of the array a, and q is the number of queries. Then a line follows containing n elements a1, a2, ..., an (0 ≤ ai ≤ 109), giving the array a.Then q lines follow, each line containing a query in the format described in the problem statement. It is guaranteed that the following constraints hold for the first type of queries: 1 ≤ p ≤ n, 0 ≤ v ≤ 109.The sum of n and q overall test cases does not exceed 106 for each. ## Output For each query of the second type, print the minimum number of required operations to convert array a to a zero array. The queries must be answered in the order given in the input. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the width of a $ 3 \times n $ grid. Let $ a_n $ denote the number of distinct ways to tile the grid using $ 1 \times 2 $ dominoes. **Constraints** $ 1 \leq n \leq 10^7 $ **Objective** Compute $ a_n \mod (10^9 + 7) $, where $ a_n $ satisfies the recurrence: $$ a_1 = 0, \quad a_2 = 3, \quad a_n = 4a_{n-2} - a_{n-4} \quad \text{for } n \geq 4 $$ with $ a_n = 0 $ for odd $ n $, and $ a_n $ defined only for even $ n \geq 2 $.

API Response (JSON)

{
  "problem": {
    "name": "A. Zero Array",
    "description": {
      "content": "You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow: A zero array is defined as an array which all its elements are zeros. There is only one al",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10185A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow:\n\nA zero array is defined as an array which all its elements are zeros. There is only one al...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the width of a $ 3 \\times n $ grid.  \nLet $ a_n $ denote the number of distinct ways to tile the grid using $ 1 \\times 2 $ dominoes.\n\n**Constraints**  \n$ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments