Two pointer 2C

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
PhanDinhKhoi
Dạng bài
Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Given an array of \(n\) integers \(a_i\). Let's say that the segment of this array \(a[l..r] (1≤l≤r≤n)\) is good if the sum of elements on this segment is at most \(s\). Your task is to find the number of good segments.

Input

  • The first line contains integers \(n\) and \(s\) \((1≤n≤10^5, 1≤s≤10^{18})\).
  • The second line contains integers \(a_i (1≤a_i≤10^9)\).

Output

  • The number of good segments.

Example

Input

7 20
2 6 4 3 6 8 9

Output

19

Nguồn: Codeforces

Bình luận

  • minhskibidi • 3:40 p.m. 16 Tháng 12, 2024 • ← chỉnh sửa 13

    Dịch đề:
    Cho 1 đoạn \(a_i\) có n phần tử. Gọi đoạn con \(a[l..r]\) \((1 \leq l \leq r \leq n)\) là đẹp nếu tổng của cả đoạn con không lớn hơn \(s\). Nhiệm vụ của bạn là đếm số đoạn con đẹp trong mảng.

    Input

    • Dòng đầu chứa số nguyên \(n\) và \(s\) \((1 \leq n \leq 10^5, 1 \leq s \leq 10^{18})\)
    • Dòng thứ hai chứa số nguyên \(a_i\) \((1 \leq a_i \leq 10^9)\)

    Output

    • Số đoạn con đẹp

    Example

    Input

    7 20
2 6 4 3 6 8 9

    Output

    19

    5
    Phản hồi