CSES - Two pointers

Có \(n\) đứa trẻ muốn đi đến một bánh xe Ferris, và nhiệm vụ của bạn là tìm một chiếc gondola cho mỗi đứa trẻ.

Mỗi chiếc gondola có thể có một hoặc hai đứa trẻ trong đó, và ngoài ra, tổng trọng lượng trong một chiếc gondola không được vượt quá \(x\). Bạn biết cân nặng của mỗi đứa trẻ.

Số lượng chiếc gondola tối thiểu cần thiết cho những đứa trẻ là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đứa trẻ và trọng lượng tối đa cho phép
• Dòng tiếp theo chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\): trọng lượng của mỗi đứa trẻ

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq x \leq 10^9\)
• \(1 \leq p_i \leq x\)

Output

• In một số nguyên: số lượng gondola tối thiểu

Example

4 10
7 2 3 9

3

Có \(n\) người đăng ký và \(m\) căn hộ trống. Nhiệm vụ của bạn là phân phối các căn hộ để nhiều người có căn hộ nhất có thể.

Mỗi người đăng ký có một kích thước căn hộ mong muốn, và họ sẽ chấp nhận bất kỳ căn hộ nào có kích thước đủ gần với kích thước mong muốn.

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\) và \(k\): số lượng người đăng ký, số lượng căn hộ và chênh lệch tối đa cho phép.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): kích thước căn hộ mong muốn của mỗi người đăng ký. Nếu kích thước mong muốn của người đăng ký là \(x\), người đó sẽ chấp nhận bất kỳ căn hộ nào có kích thước từ \(x-k\) đến \(x+k\).
• Dòng cuối cùng chứa \(m\) số nguyên \(b_1,b_2,\ldots,b_m\): kích thước của mỗi căn hộ.

Constraints

• \(1 \leq n, m \leq 2\cdot 10^5\)
• \(0 \leq k \leq 10^9\)
• \(1 \leq a_i, b_i \leq 10^9\)

Output

• In một số nguyên: số lượng người sẽ có được một căn hộ.

Example

4 3 5
60 45 80 60
30 60 75

2

Cho một mảng gồm \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\)
• Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng
• Các ràng buộc:
  • \(1 \leq n \leq 2\cdot 10^5\)
  • \(1 \leq x, a_i \leq 10^9\)

Output

• In một số nguyên: số lượng đoạn con được yêu cầu

Example

5 7
2 4 1 2 7

3

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\)
• Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng

Constraints

• \(1 \leq n \leq 2\cdot 10^5\)
• \(-10^9 \leq x, a_i \leq 10^9\)

Output

• In một số nguyên: số lượng đoạn con được yêu cầu

Example

5 7
2 -1 3 5 -2

2

Cho biết danh sách phát của một đài phát thanh kể từ khi thành lập. Danh sách phát có tổng cộng \(n\) bài hát.

Dãy các bài hát liên tiếp dài nhất, mà mỗi bài trong đó đều độc nhất là dãy nào?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng bài hát
• Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): mã số của mỗi bài hát

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq k_i \leq 10^9\)

Output

• In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất

Example

8
1 2 1 3 2 7 4 2

5

Với một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tính toán số lượng đoạn con có nhiều nhất \(k\) giá trị phân biệt.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng giá trị phân biệt tối đa
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng
• Các ràng buộc:
  • \(1 \leq k \leq n \leq 2\cdot 10^5\)
  • \(1 \leq x_i \leq 10^9\)

Output

• In một số nguyên: số lượng đoạn con.

Example

5 2
1 2 3 1 1

10