2086B.md (2412B)
1 Source: https://codeforces.com/problemset/problem/2086/B 2 3 B. Large Array and Segments 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is an array $a$ consisting of $n$ positive integers, and a positive integer $k$. An array $b$ is created from array $a$ according to the following rules: 22 23 * $b$ contains $n \cdot k$ numbers; 24 * the first $n$ numbers of array $b$ are the same as the numbers of array $a$, that is, $b_{i} = a_{i}$ for $i \le n$; 25 * for any $i \gt n$, it holds that $b_{i} = b_{i - n}$. 26 27 For example, if $a = [2, 3, 1, 4]$ and $k = 3$, then $b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4]$. 28 29 Given a number $x$, it is required to count the number of such positions $l$ ($1 \le l \le n \cdot k$), for which there exists a position $r \ge l$, such that the sum of the elements of array $b$ on the segment $[l, r]$ is at least $x$ (in other words, $b_{l} + b_{l+1} + \dots + b_{r} \ge x$). 30 31 Input 32 33 Each test consists of several test cases. The first line contains one integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. The description of the test cases follows. 34 35 The first line of each test case contains three integers $n$, $k$, $x$ ($1 \le n, k \le 10^{5}$; $1 \le x \le 10^{18}$). 36 37 The second line of each test case contains $n$ integers $a_{i}$ ($1 \le a_{i} \le 10^{8}$). 38 39 Additional constraints on the input: 40 41 * the sum of $n$ across all test cases does not exceed $2 \cdot 10^{5}$; 42 * the sum of $k$ across all test cases does not exceed $2 \cdot 10^{5}$. 43 44 Output 45 46 For each test case, output one integer — the number of suitable positions $l$ in the array $b$. 47 48 Example 49 50 Input 51 52 ``` 53 7 54 55 5 3 10 56 57 3 4 2 1 5 58 59 15 97623 1300111 60 61 105 95 108 111 118 101 95 118 97 108 111 114 97 110 116 62 63 1 100000 1234567891011 64 65 1 66 67 1 1 1 68 69 1 70 71 1 1 1 72 73 2 74 75 2 1 2 76 77 1 1 78 79 2 1 5 80 81 2 1 82 ``` 83 84 Output 85 86 ``` 87 12 88 1452188 89 0 90 1 91 1 92 1 93 0 94 ``` 95 96 Note 97 98 In the first test case, the array $b$ looks like this: 99 100 $$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5]$$ 101 102 There are $12$ positions $l$ for which there exists a suitable position $r$. Here are some (not all) of them: 103 104 * $l = 1$, for which there is a position $r = 6$, the sum over the segment $[1, 6]$ equals $18$; 105 * $l = 2$, for which there is a position $r = 5$, the sum over the segment $[2, 5]$ equals $12$; 106 * $l = 6$, for which there is a position $r = 9$, the sum over the segment $[6, 9]$ equals $10$.