Tìm kiếm nhị phân cơ bản

Cho mảng \(A\) gồm \(n\) số nguyên dương. Hãy đếm số lượng dãy con liên tiếp có tổng không nhỏ hơn \(k\).

Input

• Dòng đầu tiên gồm 2 số nguyên \(n\) và \(k\).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(A_i\) cách nhau bởi dấu cách.

Output

• In ra một số nguyên duy nhất là số lượng dãy con liên tiếp có tổng không nhỏ hơn \(k\).

Constraints

• \(1 \le n \le 10^5\).
• \(1 \le A_i \le 10^9\).
• \(1 \le k \le 10^{14}\).

Hint:

• Bài toán này chúng ta đã giải quyết bằng thuật toán Hai con trỏ với độ phức tạp O(n). Nếu hai con trỏ luôn duy trì cửa sổ L, R có tổng luôn nhỏ K. Và cửa sổ này đóng góp vào đáp án một lượng L - 1. Hãy tư duy với mỗi R làm sao để tìm được vị trí L tương ứng như thuật toán hai con trỏ.

Example

4 6
2 4 1 5

5

Trong quá trình phân tích chuỗi dữ liệu, hệ thống thu thập được một mảng \(A\) bao gồm \(n\) số nguyên. Để phục vụ cho việc khai phá thông tin, bạn được giao nhiệm vụ xây dựng một module trả lời \(q\) truy vấn từ người dùng.

Cụ thể, mỗi truy vấn sẽ cung cấp cho bạn một bộ ba tham số \((l, r, x)\). Nhiệm vụ của bạn là phải đếm xem giá trị mục tiêu \(x\) xuất hiện bao nhiêu lần nếu chỉ xét các phần tử nằm từ vị trí thứ \(l\) đến vị trí thứ \(r\) (bao gồm cả hai điểm mút) trong mảng \(A\).

Hint

• Nhận thấy giá trị x không quá \(10^5\). Ta sẽ làm gì nếu phân hoạch các phần tử của mảng thành các nhóm.
• Nếu ta có Group[x] là vector danh sách các vị trí của giá trị x trong mảng \(a\) thì thuật toán tìm kiếm nhị phân sẽ được thực thi như thế nào.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) đại diện cho kích thước mảng dữ liệu và số lượng truy vấn cần xử lý.
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) phân tách nhau bằng một khoảng trắng.
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(l, r, x\) mô tả các tham số của một truy vấn.

Output

• In ra \(q\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là kết quả thống kê tương ứng cho truy vấn thứ \(i\).

Điều kiện

• \(1 \le n, q \le 10^5\).
• \(1 \le A_i, x \le 10^5\).
• \(1 \le l \le r \le n\).

Example

6 3
1 2 2 3 2 1
1 5 2
2 4 1
4 6 1

3
0
1

Một nhà máy bánh kẹo sản xuất \(n\) loại kẹo khác nhau. Quá trình thống kê cho thấy, loại kẹo thứ \(i\) được sản xuất với số lượng là \(a_i\) chiếc, và mỗi viên kẹo loại này đều có khối lượng chuẩn là \(w_i\). Đảm bảo rằng không có bất kỳ hai loại kẹo nào có cùng khối lượng với nhau.

Sau khi sản xuất, toàn bộ số kẹo được đưa lên một băng chuyền lớn và được hệ thống tự động sắp xếp thành một hàng ngang theo thứ tự khối lượng không giảm (từ nhẹ nhất đến nặng nhất).

Bộ phận kiểm định chất lượng cần thực hiện \(q\) truy vấn kiểm tra độc lập. Trong mỗi truy vấn, họ cung cấp một số nguyên \(k\) và muốn biết: Viên kẹo nằm ở vị trí thứ \(k\) trên băng chuyền có khối lượng là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(w_i\) mô tả số lượng và khối lượng của loại kẹo thứ \(i\).
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(k\) đại diện cho một truy vấn vị trí.

Output

• In ra \(q\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là khối lượng của viên kẹo ở vị trí thứ \(k\) tương ứng với truy vấn thứ \(i\).

Constraints

• \(1 \le n, q \le 10^5\).
• \(1 \le a_i, w_i \le 10^9\).
• \(1 \le k \le a_1 + a_2 + \dots + a_n \le 10^{14}\).

Example

3 3
2 10
3 5
1 15
1
4
6

5
10
15

Một công ty logistics cần vận chuyển \(n\) kiện hàng đến các đại lý theo đúng thứ tự đã được sắp xếp trước. Kiện hàng thứ \(i\) có khối lượng là \(A_i\) kilogram.

Để hoàn thành đơn hàng, công ty sẽ sử dụng chính xác \(k\) xe tải. Mỗi xe phải chở một đoạn các kiện hàng liên tiếp, và mỗi kiện hàng chỉ được giao bởi đúng một xe.

Khối lượng mà một xe phải chở bằng tổng khối lượng các kiện hàng được giao cho xe đó.

Do giới hạn tải trọng của xe, công ty muốn phân chia các kiện hàng sao cho xe phải chở nhiều hàng nhất có khối lượng nhỏ nhất có thể.

Hãy xác định tải trọng lớn nhất tối thiểu đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le k \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^9\)).

Output

• Một số nguyên duy nhất là tải trọng lớn nhất tối thiểu tìm được.

Example

5 3
1 2 3 4 5

6

Constraints

• \(1 \le k \le n \le 10^5\).
• \(1 \le A_i \le 10^9\).

Tại một trang trại chăn nuôi gia cầm quy mô lớn, người chủ trang trại vừa nhận được một đơn đặt hàng khẩn cấp từ một nhà hàng nổi tiếng. Nhà hàng này cần đúng \(M\) quả trứng để chuẩn bị cho một bữa tiệc quan trọng.

Trang trại hiện có \(N\) con gà, được đánh số từ \(1\) đến \(N\). Mỗi con gà có tốc độ đẻ trứng khác nhau: con gà thứ \(i\) cần đúng \(T_i\) giây để sản xuất ra một quả trứng. Điều này có nghĩa là con gà thứ \(i\) sẽ đẻ trứng vào các thời điểm \(T_i, 2 \cdot T_i, 3 \cdot T_i, \dots\) tính từ lúc bắt đầu.

Với tư cách là quản lý trang trại, bạn hãy tính toán xem cần ít nhất bao nhiêu thời gian để tất cả các con gà cùng nhau sản xuất đủ (hoặc nhiều hơn) \(M\) quả trứng cung cấp cho nhà hàng.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) (\(1 \le N \le 10^5, 1 \le M \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(T_1, T_2, \dots, T_N\) (\(1 \le T_i \le 10^9\)).

Output

• Một số nguyên duy nhất là thời gian tối thiểu cần thiết.

Example

2 7
3 2

9

3 10
1 2 3

6

Constraints

• Subtask \(1\) (\(30\%\) số điểm): \(N, M, T_i \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Một khu rừng có \(n\) cây tre, cây thứ \(i\) có chiều cao là \(H_i\) mét.

Để phục vụ sản xuất, người quản lý sử dụng một chiếc máy cắt có thể điều chỉnh độ cao lưỡi cắt. Máy được đặt ở độ cao \(H\) mét so với mặt đất.

• Những cây có chiều cao không vượt quá \(H\) sẽ không bị cắt.
• Những cây cao hơn \(H\) sẽ bị cắt phần ngọn, và lượng tre thu được từ cây đó là \(H_i - H\) mét.

Nhà máy cần ít nhất \(M\) mét tre để đáp ứng đơn hàng.

Hãy tìm độ cao đặt lưỡi cắt lớn nhất sao cho tổng lượng tre thu được không nhỏ hơn \(M\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(M\).
• Dòng thứ hai chứa \(n\) số nguyên \(H_1, H_2, \dots, H_n\).

Output

• In ra một số nguyên duy nhất là độ cao đặt lưỡi cắt lớn nhất thỏa mãn yêu cầu.

Constraints

• \(1 \le n \le 10^6\).
• \(1 \le M \le 2 \cdot 10^9\).
• \(1 \le H_i \le 10^9\).

Example

4 7
20 15 10 17

15

Có \(n\) người bạn đứng trên trục tọa độ \(Ox\). Người thứ \(i\) đứng ở vị trí \(x_i\) và có thể di chuyển với vận tốc tối đa là \(v_i\). Tìm thời gian ngắn nhất \(t\) để tất cả \(n\) người có thể tụ họp tại cùng một điểm.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 6 \cdot 10^4\)).
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) (\(1 \le x_i \le 10^9\)) — tọa độ của những người bạn.
• Dòng thứ ba chứa \(n\) số nguyên \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)) — vận tốc tối đa của những người bạn.

Output

• In ra một số thực duy nhất là thời gian tối thiểu để tất cả mọi người gặp nhau. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá \(10^{-6}\).

Constraints

• \(1 \le n \le 6 \cdot 10^4\)
• \(1 \le x_i, v_i \le 10^9\)

Example

3
7 1 3
1 2 1

2.000000000000

4
5 10 3 2
2 3 2 4

1.400000000000

Phân tích

• Hàm đơn điệu ở đây là thời gian. Nếu trong thời gian \(t\) họ có thể gặp nhau, thì \(t + \epsilon\) họ cũng gặp nhau được.
• Ta chặt nhị phân thời gian \(t\). Với một mức thời gian \(t\) cố định, phạm vi di chuyển của người thứ \(i\) là một đoạn thẳng \([x_i - v_i \cdot t, x_i + v_i \cdot t]\).
• Để tất cả gặp nhau, giao của \(n\) đoạn thẳng này phải khác rỗng. Nghĩa là:
  
  \[ \max(x_i - v_i \cdot t) \le \min(x_i + v_i \cdot t) \]

Cho mảng \(a\) gồm \(n\) phần tử, hãy tìm một đoạn con liên tiếp có độ dài tối thiểu là \(d\) sao cho trung bình cộng của các phần tử trong đoạn con đó là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(d\) (\(1 \le d \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^6\)).

Output

• In ra một số thực duy nhất là giá trị trung bình cộng lớn nhất tìm được. Kết quả được chấp nhận nếu có sai số không quá \(10^{-6}\).

Example

4 2
3 4 1 2

3.500000

Phân tích (Idea)

• Đây là dạng bài "Maximum Average" cực kỳ kinh điển. Ta sử dụng phương pháp chặt nhị phân giá trị trung bình \(x\).
• Ta cần kiểm tra xem có đoạn con nào độ dài \(\ge d\) thỏa mãn:
  
  \[ \frac{a_l + a_{l+1} + \dots + a_r}{r - l + 1} \ge x \]
• Biến đổi bất phương trình:
  
  \[ (a_l - x) + (a_{l+1} - x) + \dots + (a_r - x) \ge 0 \]
• Đến đây, bài toán trở thành tìm đoạn con có độ dài \(\ge d\) mang tổng \(\ge 0\) trên mảng mới \(b_i = a_i - x\). Sử dụng mảng cộng dồn (prefix sum) và kỹ thuật duy trì min prefix sum có thể giải quyết trong \(O(n)\).