CSES - Sorting and Searching 1

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị của mảng.

Output

• In một số nguyên duy nhất là tổng đoạn con lớn nhất.

Constraints

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

Example

8
-1 3 -2 5 3 -5 2 2

9

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

Có \(n\) que với một số độ dài. Nhiệm vụ của bạn là sửa đổi các que sao cho mỗi que có cùng chiều dài.

Bạn có thể kéo dài và rút ngắn từng thanh. Cả hai thao tác đều có chi phí \(x\) trong đó \(x\) là chênh lệch giữa độ dài mới và độ dài ban đầu.

Tổng chi phí tối thiểu là bao nhiêu?

Input

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng que
• Dòng thứ hai chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\): độ dài của các que

Constraints

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

Output

• In một số nguyên: tổng chi phí tối thiểu

Example

5
2 3 1 5 2

5

Bạn có \(n\) đồng xu với các giá trị nguyên dương. Số tiền nhỏ nhất bạn không thể tạo bằng cách sử dụng một tập hợp con của các đồng xu là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng đồng xu
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của mỗi đồng xu

Constraints

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

Output

• In một số nguyên: tổng tiền xu nhỏ nhất

Example

5
2 9 1 2 7

6

Bạn được cho một mảng gồm \(n\) số nguyên và nhiệm vụ của bạn là tìm hai giá trị (tại các vị trí phân biệt) có tổng là \(x\).

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước mảng và tổng mong muốn
• Dòng thứ hai có \(n\) số nguyên \(a_1,a_2,\ldots,a_n\): các giá trị của mảng

Constraints

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

Output

• In hai số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE

Example

4 8
2 7 5 1

2 4

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

Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thể xem trọn vẹn là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng bộ phim
• Sau đó có \(n\) dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian bắt đầu và kết thúc của một bộ phim

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)

Output

• In một số nguyên: số lượng phim tối đa

Example

3
3 5
4 9
5 8

2

Bạn được cho một danh sách gồm \(n\) số nguyên và nhiệm vụ của bạn là tính toán số lượng giá trị phân biệt trong danh sách.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng giá trị
• Dòng thứ hai có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\)

Output

• In một số nguyên: số lượng giá trị phân biệt

Constraints

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

Example

5
2 3 2 2 3

2

Có \(n\) vé hòa nhạc có sẵn, mỗi vé có một mức giá nhất định. Sau đó, \(m\) khách hàng đến, lần lượt đến.

Mỗi khách hàng thông báo mức giá tối đa mà họ sẵn sàng trả cho một vé, và sau đó, họ sẽ nhận được một vé với giá lớn nhất có thể sao cho nó không vượt quá giá tối đa.

Input

• Dòng đầu vào đầu tiên chứa các số nguyên \(n\) và \(m\): số lượng vé và khách hàng
• Dòng tiếp theo chứa \(n\) số nguyên \(h_1,h_2,\ldots,h_n\): mức giá của mỗi vé
• Dòng cuối cùng chứa \(m\) số nguyên \(t_1,t_2,\ldots,t_m\): mức giá tối đa của mỗi khách hàng theo thứ tự họ đến

Constraints

• \(1 \leq n,m \leq 2 \cdot 10^5\)
• \(1 \leq h_i,t_i \leq 10^9\)

Output

• In, đối với mỗi khách hàng, mức giá mà họ sẽ trả cho vé của họ. Sau này, vé không thể được mua lại
• Nếu khách hàng không thể nhận được bất kỳ vé nào, hãy in \(-1\)

Example

5 3
5 3 7 8 5
4 8 3

3
8
-1

Bạn được cho thời gian đến và rời đi của \(n\) khách hàng trong một nhà hàng.

Số lượng khách hàng tối đa trong nhà hàng bất cứ lúc nào là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng khách hàng.
• Sau này, có \(n\) dòng mô tả khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian đến và rời của khách hàng.
• Bạn có thể giả định rằng tất cả thời gian đến và đi là khác nhau.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)

Output

• In một số nguyên: số lượng khách hàng tối đa.

Example

3
5 8
2 4
3 9

2