Đếm đoạn có tổng K (Count Interval)

Nguồn: AtCoder

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

Đề bài

Cho dãy số nguyên

và số nguyên $K$.

Hãy đếm số cặp chỉ số $(l,r)$ thỏa

và tổng của đoạn liên tiếp từ $l$ đến $r$ bằng đúng $K$:

Input

• Dòng đầu chứa hai số nguyên $N,K$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In số cặp $(l,r)$ thỏa mãn điều kiện.

Subtask

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

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

• $|A_i|\le10^9$

• $|K|\le10^{15}$

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

• Subtask 2 — 30%: $N\le3000$.

• 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

6 5
8 -3 5 7 0 -4

Output

3

Giải thích

Với $K=5$ và dãy

ba đoạn có tổng bằng $5$ là:

• $[1,2]$: $8-3=5$;
• $[2,6]$: $-3+5+7+0-4=5$;
• $[3,3]$: phần tử duy nhất bằng $5$.

Do đó đáp án là $3$.