codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1994C.md (2390B)


      1 Source: https://codeforces.com/problemset/problem/1994/C
      2 
      3 C. Hungry Games
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Yaroslav is playing a computer game, and at one of the levels, he encountered $n$ mushrooms arranged in a row. Each mushroom has its own level of toxicity; the $i$-th mushroom from the beginning has a toxicity level of $a_i$. Yaroslav can choose two integers $1 \le l \le r \le n$, and then his character will take turns from left to right to eat mushrooms from this subsegment one by one, i.e., the mushrooms with numbers $l, l+1, l+2, \ldots, r$.
     22 
     23 The character has a toxicity level $g$, initially equal to $0$. The computer game is defined by the number $x$ — the maximum toxicity level at any given time. When eating a mushroom with toxicity level $k$, the following happens:
     24 
     25 1. The toxicity level of the character is increased by $k$.
     26 2. If $g \leq x$, the process continues; otherwise, $g$ becomes zero and the process continues.
     27 
     28 Yaroslav became interested in how many ways there are to choose the values of $l$ and $r$ such that the final value of $g$ is not zero. Help Yaroslav find this number!
     29 
     30 Input
     31 
     32 Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. Then follows the description of the test cases.
     33 
     34 The first line of each test case contains two integers $n$, $x$ ($1 \leq n \leq 2 \cdot 10^5, 1 \le x \le 10^9$) — the number of mushrooms and the maximum toxicity level.
     35 
     36 The second line of each test case contains $n$ numbers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).
     37 
     38 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, output a single number — the number of subsegments such that the final value of $g$ will not be zero.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 4 2
     52 
     53 1 1 1 1
     54 
     55 3 2
     56 
     57 1 2 3
     58 
     59 1 6
     60 
     61 10
     62 
     63 6 3
     64 
     65 1 2 1 4 3 8
     66 
     67 5 999999999
     68 
     69 999999999 999999998 1000000000 1000000000 500000000
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 8
     76 2
     77 0
     78 10
     79 7
     80 ```
     81 
     82 Note
     83 
     84 In the first test case, the subsegments $(1, 1)$, $(1, 2)$, $(1, 4)$, $(2, 2)$, $(2, 3)$, $(3, 3)$, $(3, 4)$ and $(4, 4)$ are suitable.
     85 
     86 In the second test case, non-zero $g$ will remain only on the subsegments $(1, 1)$ and $(2, 2)$.
     87 
     88 In the third test case, on the only possible subsegment, $g$ will be zero.