{"problem":{"name":"Subsegments with Small Sums","description":{"content":"You are given a positive integer $S$. For a sequence of positive integers $x$, we define $f(x)$ as follows: *   Consider decomposing $x$ into several contiguous subsequences. For each contiguous subs","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc169_b"},"statements":[{"statement_type":"Markdown","content":"You are given a positive integer $S$. For a sequence of positive integers $x$, we define $f(x)$ as follows:\n\n*   Consider decomposing $x$ into several contiguous subsequences. For each contiguous subsequence, the sum of its elements must be **at most** $S$. The minimum number of contiguous subsequences in such a decomposition is the value of $f(x)$.\n\nIt can be proved that the value of $f$ is always definable under the constraints of this problem.\nYou are given a sequence of positive integers $A=(A_1,A_2,\\cdots,A_N)$. Find the value of $\\sum_{1 \\leq l \\leq r \\leq N} f((A_l,A_{l+1},\\cdots,A_r))$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 250000$\n*   $1 \\leq S \\leq 10^{15}$\n*   $1 \\leq A_i \\leq \\min(S,10^9)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $S$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc169_b","tags":[],"sample_group":[["3 3\n1 2 3","8\n\nFor example, consider $x=(1,2,3)$. The decomposition $(1,2),(3)$ satisfies the condition, and no decomposition into fewer than two contiguous subsequences satisfies the condition, so $f((1,2,3))=2$.\nShown below are the possible $l,r$ and the corresponding values of $f$:\n\n*   $(l,r)=(1,1)$: $f((1))=1$\n*   $(l,r)=(1,2)$: $f((1,2))=1$\n*   $(l,r)=(1,3)$: $f((1,2,3))=2$\n*   $(l,r)=(2,2)$: $f((2))=1$\n*   $(l,r)=(2,3)$: $f((2,3))=2$\n*   $(l,r)=(3,3)$: $f((3))=1$\n\nThus, the answer is $1+1+2+1+2+1=8$."],["5 1\n1 1 1 1 1","35"],["5 15\n5 4 3 2 1","15"],["20 1625597454\n786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130","588"]],"created_at":"2026-03-03 11:01:14"}}