{"problem":{"name":"C. Daniel's game","description":{"content":"On a beautiful day in December, Daniel invites Andy to play an interesting game: Daniel will pick an array $A$ which has $n$ non-negative integers $A_1, A_2,..., A_n$ and a non-negative integer $M$. A","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10245C"},"statements":[{"statement_type":"Markdown","content":"On a beautiful day in December, Daniel invites Andy to play an interesting game: Daniel will pick an array $A$ which has $n$ non-negative integers $A_1, A_2,..., A_n$ and a non-negative integer $M$. After that, Andy will randomly pick a non-empty sub-array of $A$, which means he will pick two integers $l, r \" \"(1 <= l <= r <= n)$ và take $A_l, A_{l + 1},..., A_r$ from the array $A$. Andy has to preserve the order of the taken integers.\n\nAndy is only allowed to increase his taken integers. Suppose after doing so he receives $A '_l, A '_(l + 1),..., A '_r$ where $A '_i in ZZ, \" \"A '_i >= A_i forall i = overline(l , r)$. However, he must follow the restriction below:\n\n$$\\sum_{i=l}^{r} A'_i - A_i\\le M$$.\n\nIf $A '_l, A '_(l + 1),..., A '_r$ in this order form a non-decreasing array, Daniel will award Andy with bubble tea.\n\nRight after Andy accepts the challenge, Daniel thinks hard to lower the chance of Andy winning as much as possible. Therefore, when he thinks of array $A$, Daniel has to calculate quickly the number of non-empty sub-arrays of $A$ that Andy can pick to win this game.\n\nAfter $frac(21, 10)$ second, Daniel has to start the game by telling Andy the array. Please help him to calculate in 2 secs.\n\nLine 1 contains 2 integers $n, M$.\n\nLine 2 contains $n$ integers of array $A$: $A_1, A_2,..., A_n$.\n\nNumbers on the same line are separated by spaces\n\nAn integer indicating the answer\n\nIn all testcases, $n >= 1, 0 <= M <= 2 times 10^(14), 0 <= A_i <= 10^9 \" \"forall i = overline(1 comma n)$.\n\n70 points with 3 subtasks:\n\n## Input\n\nLine 1 contains 2 integers $n, M$.Line 2 contains $n$ integers of array $A$: $A_1, A_2,..., A_n$.Numbers on the same line are separated by spaces\n\n## Output\n\nAn integer indicating the answer\n\n[samples]\n\n## Scoring\n\nIn all testcases, $n >= 1, 0 <= M <= 2 times 10^(14), 0 <= A_i <= 10^9 \" \"forall i = overline(1 , n)$.70 points with 3 subtasks:  12 points: $n <= 100$.  18 points: $n <= 1000$.  40 points: $n <= 2 times 10^5$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ M \\in \\mathbb{Z}_{\\ge 0} $.  \nLet $ A = (A_1, A_2, \\dots, A_n) $ be a sequence of non-negative integers.\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 0 \\le M \\le 2 \\times 10^{14} $  \n3. $ 0 \\le A_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of non-empty contiguous subarrays $ (l, r) $ with $ 1 \\le l \\le r \\le n $, for which there exists a sequence $ A' = (A'_l, A'_{l+1}, \\dots, A'_r) $ satisfying:  \n- $ A'_i \\in \\mathbb{Z} $ and $ A'_i \\ge A_i $ for all $ i \\in \\{l, \\dots, r\\} $,  \n- $ \\sum_{i=l}^{r} (A'_i - A_i) \\le M $,  \n- $ A'_l \\le A'_{l+1} \\le \\dots \\le A'_r $ (non-decreasing).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10245C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}