LQDOJ CUP 2023 - Round 3

Một ngày nọ, phòng kỹ thuật của một công ty được yêu cầu phải thực hiện \(m\) công việc, công việc thứ \(i\) có \(k_i\) phần. Họ phải hoàn thành hết tất cả công việc đó trong vòng \(n\) ngày được đánh số từ ngày \(1\) đến ngày \(n\). Được biết phòng kỹ thuật có một siêu máy tính có thể chứa rất nhiều lõi. Mỗi lõi có khả năng thực hiện và hoàn thành một phần của một công việc bất kỳ trong đúng một ngày, các phần của một công việc có thể được thực hiện và hoàn thành một cách song song và không cần liên tiếp (tức là có thể thực hiện các phần trong một hoặc nhiều ngày). Một công việc được hoàn thành khi và chỉ khi tất cả các phần của công việc đó được hoàn thành. Biết rằng công việc thứ \(i\) chỉ có thể được thực hiện và hoàn thành từ đầu ngày \(s_i\) đến hết ngày \(t_i\), vì chi phí lắp đặt và bảo trì rất tốn kém nên trưởng phòng kỹ thuật muốn sử dụng ít lõi nhất có thể.

Yêu cầu: Tính số lượng lõi ít nhất cần phải lắp đặt sao cho vẫn đảm bảo hoàn thành hết \(m\) công việc trong \(n\) ngày.

Input

• Dòng đầu tiên chứa hai số nguyên \(m\) và \(n\) \((1 \leq m \leq 10^5, 1 \leq n \leq 10^9)\) lần lượt là số lượng công việc và số ngày thực hiện.
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(k_i\), \(s_i\) và \(t_i\) \((1 \leq k_i \leq 10^{12}, 1 \leq s_i \leq t_i \leq n)\) là số lượng phần và thời điểm giới hạn thực hiện công việc thứ \(i\).

Output

• In ra kết quả của yêu cầu bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(s_i = t_i\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 500\), \(n \leq 10^6\) và \(k_i \leq 500\).
• Subtask \(3\) (\(30\%\) số điểm): \(k_i = 1\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 4
3 1 3
2 2 4
4 1 4

3

4 3
1 1 3
4 3 3
2 2 3
2 1 2

4

Ngày hôm nay, các chiến sĩ thuộc Đại đội 9 đang tập luyện tập hợp đội hình trên thao trường. Thao trường có khuôn viên là một hình chữ nhật gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ trên xuống dưới từ \(1\) tới \(r\) và các cột được đánh số từ trái sang phải từ \(1\) tới \(c\). Giao của hàng \(i\) và cột \(j\) sẽ là ô vuông có tọa độ \((i, j)\). Ta định nghĩa khoảng cách giữa hai ô \((x, y)\) và \((u, v)\) sẽ bằng \(|x - u| + |y - v|\). Hiện tại, trên mỗi ô vuông sẽ có tối đa 1 chiến sĩ đang đứng. Một đội hình sẽ cần có đúng \(k\) chiến sĩ. Khi phát hiệu lệnh tập trung đội hình tại một ô \((x, y)\) nào đó, \(k\) chiến sĩ có khoảng cách từ ô đang đứng tới ô \((x, y)\) là ngắn nhất sẽ di chuyển tới ô này (tính cả chiến sĩ đang đứng tại ô \((x, y)\) nếu có). Thời gian di chuyển của một chiến sĩ sẽ đúng bằng khoảng cách giữa hai ô.

Yêu cầu: Với mỗi ô \((x, y)\) nằm trong khuôn viên của thao trường, hãy tính tổng thời gian di chuyển của \(k\) chiến sĩ sẽ thực hiện xếp đội hình nếu ta phát hiệu lệnh tập trung tại ô này.

Input

• Dòng đầu tiên chứa ba số nguyên \(r\), \(c\) và \(k\) \((1 \leq r, c \leq 2000, 1 \leq k \leq r \times c)\) lần lượt là số hàng, số cột của khuôn viên thao trường và số lượng chiến sĩ cần để tập hợp đội hình.
• Trong \(r\) dòng tiếp theo, dòng thứ \(i\) chứa \(c\) số nguyên \(a_{i, 1}, a_{i, 2}, \ldots, a_{i, c}\) \((0 \leq a_{i,j} \leq 1)\). Trong đó \(a_{i, j} = 1\) có nghĩa là có một chiến sĩ đứng tại ô \((i,j)\), ngược lại thì không.
• Dữ liệu đảm bảo số lượng chiến sĩ đang có trên thao trường sẽ không nhỏ hơn \(k\).

Output

• Để giảm kích thước dữ liệu đầu ra, gọi \(ans(x,y)\) là tổng thời gian di chuyển của \(k\) chiến sĩ sẽ thực hiện xếp đội hình nếu ta phát hiệu lệnh tập trung tại ô \((x, y)\), hãy in ra một số duy nhất là \(\sum\limits_{x = 1}^{r}\sum\limits_{y = 1}^{c}ans(x, y)\), hay nói cách khác là tổng tất cả \(ans(x, y)\) với mọi \(1 \leq x \leq r\) và \(1 \leq y \leq c\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(r, c \leq 50\).
• Subtask \(2\) (\(10\%\) số điểm): \(r, c \leq 300, k = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(r, c \leq 300\).
• Subtask \(4\) (\(20\%\) số điểm): \(r, c \leq 1000\).
• Subtask \(5\) (\(10\%\) số điểm): \(k = 1\).
• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3 2
0 0 1
1 1 0
0 1 0

17

3 2 2
1 1 2
2 1 3

5 6 3
1 0 0 1 0 1
0 1 1 0 1 0
0 0 1 0 1 0
1 0 0 1 1 1
0 0 0 1 0 1

114

5 4 4 4 3 4
4 3 2 3 3 4
5 4 3 3 2 4
6 5 4 2 2 2
8 7 5 3 3 3

Có \(n\) thùng đựng nước sôi, các thùng nước được đánh số từ \(1\) đến \(n\), thùng nước thứ \(i\) có bán kính \(b_{i}\). Dì của Tấm lấy thêm \(n\) chiếc nắp đậy, đậy các thùng nước lại. Thùng nước thứ \(i\) được đậy bởi chiếc nắp có bán kính \(a_{i}\). Dì ghẻ bắt Tấm phải thực hiện một công việc vô lý:

• Chọn hai thùng nước bất kỳ và hoán đổi nắp của chúng cho đến khi tất cả các thùng nước đều được đậy kín (được đậy bằng nắp có bán kính to hơn hoặc bằng miệng thùng) mới cho Tấm đi hội của Vua.

Hướng dẫn Tấm xong, Dì dặn dò Cám trông chừng và theo dõi Tấm làm việc đến khi đáp ứng được yêu cầu thì ả mới để Tấm đi hội. Ngoài ra, vì thích gây khó dễ, Cám bắt buộc Tấm phải làm sao cho số thùng bị đổi nắp là ít nhất, tức là số thùng không bị đổi nắp là nhiều nhất. Chớp lấy cơ hội để làm việc tốt, trong làn sương 100 độ của nước sôi, Bụt dần hiện lên và hỏi:

"Tại sao con khóc?"

Nhưng khi Bụt vừa dứt câu thì Tấm đã giải xong bài toán, thay quần áo và đi dạo hội trong sự ngỡ ngàng của Bụt và Cám.

Câu chuyện sau đó thì ai cũng biết... Nhưng không ai hiểu được vì sao Tấm lại có thể giải bài toán hóc húa ấy một cách dễ dàng như vậy.

Thời nay, với sự tiến triển vượt bậc của công nghệ và thuật toán. Bài toán năm xưa mà Tấm giải được đã được mang ra để nghiên cứu trong kỳ thi LQDOJ CUP này.

Yêu cầu: Bạn hãy viết chương trình để giải bài toán này nhằm nghiên cứu về cách mà Tấm giải được bài toán này nhé. Khác với bài toán năm xưa, dữ liệu đầu vào có thể khác với những gì mà Dì đã cho Tấm nên có thể xảy ra trường hợp không thể đổi các nắp thùng sao cho thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 3 \times 10^{5})\) lần lượt là số thùng nước và nắp đậy.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_{i}\) và \(b_{i}\) \((1 \leq a_{i}, b_{i} \leq 10^{9})\) lần lượt là bán kính của nắp đậy và bán kính của thùng nước.

Output

• In ra \(-1\) nếu không tồn tại cách hoán đổi. Ngược lại, in ra số lượng lớn nhất có thể các thùng nước không đổi nắp.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 1000\) và với mọi \(i,j\) \((1 \le i,j \le n)\) nào mà thoả mãn \(b_{i} \leq a_{i}, b_{j} \leq a_{j}, a_{i} \leq a_{j}\) thì cũng có \(b_{i} \geq b_{j}\) hoặc \(b_{i} < a_{j}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 1000\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_{i}, b_{i} \leq 100\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 1
3 3
5 2

3

5
1 2
2 4
4 5
6 1
5 3

1

2 2
4 4
6 5
1 1
5 3