Petya và mảng (Petya and Array)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $n$ số nguyên và một số nguyên $t$.

Hãy đếm số đoạn con liên tiếp không rỗng có tổng nhỏ hơn $t$.

Cụ thể, cần đếm số cặp $(l,r)$ sao cho

và

Input

• Dòng đầu chứa hai số nguyên $n,t$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In số đoạn con có tổng nhỏ hơn $t$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le2\cdot10^5$

• $|t|\le2\cdot10^{14}$

• $|a_i|\le10^9$

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: Mọi phần tử đều không âm: $a_i\ge0$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

5 4
5 -1 3 4 -1

Output

5

Giải thích

Với $t=4$ và dãy

năm đoạn có tổng nhỏ hơn $4$ là:

• $[2,2]$: tổng $-1$;
• $[2,3]$: tổng $2$;
• $[3,3]$: tổng $3$;
• $[4,5]$: tổng $3$;
• $[5,5]$: tổng $-1$.

Vì vậy đáp án là $5$.