Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arraycounting.in, arraycounting.out | Sursă | IIOT 2021-22 Runda 1 |
| Autor | Stefan Dascalescu | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Array Counting
Given an array of length n and a number k, we need to process q queries of the following types:
1 a b: Change the value of the number at position a to b
2 l r s: Find how many arrays exist which can be formed with the numbers from positions l to r, such that the value of each of the numbers is at least k and the sum of the values is equal to s, if the only operation we can make is to increase values of the numbers from the array. Since the number of arrays can be really big, print the answer mod 10^9 + 7
Date de intrare
Input file arraycounting.in will contain three integers, n, q and k, which represent the length of the array, the number of queries we need to process and the minimal threshold for the value of each number with respect to the second type of query.
The second line of the input will contain the initial array v.
The next q lines of the input will contain the description of the queries.
For queries of type 1, ($1 \le a \le n$), ($1 \le b \le 100$). For queries of type 2, ($1 \le l \le r \le n$), ($1 \le s \le 2 * 10^6$).
Date de ieşire
Output file arraycounting.out will contain a line for each query of type 2, with the answer for each query of type 2.
Restricţii
- 1 ≤ n ≤ 5 * 10^4
- 1 ≤ q ≤ 2 * 10^5
- 1 ≤ k ≤ 20
- 1 ≤ v[i], b ≤ 100
- 1 ≤ a, l, r ≤ n
- 1 ≤ s ≤ 2 * 10^6
- For tests worth 20 points, 1 ≤ n ≤ 20.
- For tests worth 40 additional points, 1 ≤ n ≤ 2000, 1 ≤ q ≤ 5000.
Exemplu
| arraycounting.in | arraycounting.out |
|---|---|
| 4 5 2 0 0 0 3 2 1 4 10 1 1 2 2 2 3 3 1 2 4 2 1 2 6 | 4 0 1 |
Explicaţie
For the first query, the arrays we can get are [2, 2, 3, 3], [2, 3, 2, 3], [3, 2, 2, 3], [2, 2, 2, 4].
