Sorting and Searching (CTDL)

Có một khách sạn lớn, và \(n\) khách hàng sẽ đến sớm. Mỗi khách hàng muốn có một phòng đơn.

Bạn biết ngày nhận phòng và trả phòng của mỗi khách hàng. Hai khách hàng có thể ở trong cùng một phòng nếu ngày trả phòng của khách hàng đầu tiên sớm hơn ngày nhận phòng của khách hàng thứ hai.

Số lượng phòng tối thiểu cần thiết để chứa tất cả khách hàng là bao nhiêu? Và các phòng có thể được phân bổ như thế nào?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng khách hàng
• Sau đó, có \(n\) dòng, mỗi dòng mô tả một khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): ngày nhận phòng và trả phòng

Constraints

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

Output

• In đầu tiên một số nguyên \(k\): số phòng tối thiểu cần thiết
• Sau đó, in một dòng chứa số phòng của mỗi khách hàng theo thứ tự giống như trong đầu vào. Các phòng được đánh số \(1,2,\ldots,k\). Bạn có thể in bất kỳ giải pháp hợp lệ nào

Example

3
1 2
2 4
4 4

2
1 2 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

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

Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Câu lạc bộ phim của Syrjälä bao gồm \(k\) thành viên, tất cả sẽ tham dự lễ hội phim.

Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Tổng số phim tối đa mà các thành viên câu lạc bộ có thể xem hoàn toàn là bao nhiêu nếu họ hành động tối ưu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\): số lượng phim và thành viên câu lạc bộ
• Sau này, 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 k \leq n \leq 2\cdot 10^5\)
• \(1 \leq a < b \leq 10^9\)

Output

• In một số nguyên: tổng số bộ phim tối đa

Example

5 2
1 5
8 10
3 6
2 5
6 9

4

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. Nhiệm vụ của bạn là tính nội dung của mảng sau \(k\) vòng sắp xếp nổi bọt.

Trong một vòng, ta duyệt mảng từ trái sang phải và hoán đổi hai phần tử kề nhau nếu chúng đang sai thứ tự.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước mảng và số vòng.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): các phần tử của mảng.

Output

• In ra \(n\) số nguyên: nội dung của mảng sau \(k\) vòng.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(0 \le k \le 10^9\)
• \(1 \le x_i \le 10^9\)

Example

5 2
3 2 4 1 4

2 1 3 4 4

Trải qua quá nhiều năm thăng trầm trong đầu tư chứng khoán, Nam đã trở thành một bậc thầy đầu tư. Hơn cả thế, Nam còn có năng lực dự đoán tương lai và biết trước được giá cổ phiếu IVN sẽ lên xuống \(n\) lần trong hôm nay. Cụ thể, Nam biết trước nếu "vào lệnh" vào đợt thứ \(i\) thì sẽ đem lại lợi nhuận là \(a_i\) VNĐ. Nếu \(a_i\) âm nghĩa là Nam sẽ thua lỗ \(-a_i\) VNĐ khi vào lệnh ở đợt \(i\).
Tuy nhiên, vì đã quá giàu nên Nam không muốn tổng lợi nhuận là lớn nhất. Thay vào đó, Nam muốn độ "chất chơi" phải cao, tức là đặt lệnh vào càng nhiều đợt càng tốt, kể cả có những đợt âm rất nhiều tiền (và dù Nam đã biết trước điều đó!). Để không bị đánh giá là đầu tư thiếu thông minh, Nam muốn đảm bảo sau mỗi lần vào lệnh, tổng lợi nhuận thu được là không âm.
Là một trợ lý mới được tuyển dụng, bạn được Nam nhờ tính độ "chất chơi".

Input

• Dòng đầu tiên chứa \(n\) \((1 \le n \le 2.10^5)\): số đợt thay đổi của cổ phiếu
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n (-10^9 \le a_i \le 10^9)\): nếu Nam vào lệnh ở đợt thứ \(i\) thì tổng lợi nhuận tăng lên \(a_i\).

Output

• Dòng duy nhất chứa số lần vào lệnh nhiều nhất có thể, thỏa mãn yêu cầu trên.

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \le n \le 20\)
• Subtask 2 (\(40\%\) số điểm): \(1 \le n \le 1000\)
• Subtask 3 (\(20\%\) số điểm): Không có giới hạn thêm.

6
4 -4 1 -3 1 -3

5