BOI 2024 - Ngày 2

Trong tín ngưỡng Baltic cổ, việc giữ cho ngọn lửa thiêng luôn cháy có ý nghĩa quan trọng. Một vị tư tế được gọi là krivis có trách nhiệm bảo vệ ngọn lửa, không để nó tắt. Ông có nhiều nữ trợ tá đáng tin cậy, được gọi là vaidilutės, và muốn lập lịch để họ tiếp lửa và trông coi ngọn lửa. Ông phải bảo đảm luôn có một vaidilutė chăm sóc ngọn lửa.

Krivis sử dụng hệ thống đo thời gian riêng, trong đó mỗi ngày có \(M\) phút. Trong làng có \(N\) vaidilutės. Khoảng thời gian mà vaidilutė thứ \(i\) có thể làm việc được mô tả bởi hai số nguyên \(s_i\) và \(e_i\). Số \(s_i\) là thời điểm sớm nhất trong ngày mà cô có thể bắt đầu làm việc, còn \(e_i\) là thời điểm muộn nhất trong ngày mà cô phải kết thúc công việc. Thời gian được tính bằng số phút kể từ đầu ngày. Lưu ý rằng nếu \(s_i>e_i\), cô sẵn sàng làm việc qua đêm.

Krivis nhờ bạn chọn một số vaidilutės và sắp xếp ca làm việc cho họ. Mỗi vaidilutė được chọn phải bắt đầu ca không sớm hơn \(s_i\) và kết thúc ca không muộn hơn \(e_i\). Một ca làm việc luôn ngắn hơn một ngày trọn vẹn. Những vaidilutės được chọn sẽ lặp lại ca làm việc của mình hằng ngày.

Việc bàn giao công việc giữa hai vaidilutės làm tăng nguy cơ ngọn lửa bị tắt. Vì vậy, bạn muốn giảm thiểu số lần bàn giao trong ngày bằng cách lập lịch cần ít vaidilutės nhất có thể.

Hãy tính số vaidilutės ít nhất cần chọn để ngọn lửa thiêng được chăm sóc tại mọi thời điểm.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số vaidilutės có thể làm việc và số phút trong một ngày.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(s_i\) và \(e_i\), lần lượt là thời điểm bắt đầu sớm nhất và thời điểm kết thúc muộn nhất của vaidilutė thứ \(i\).

Dữ liệu ra

In ra một số nguyên là số vaidilutės ít nhất cần chọn. Nếu không thể chọn các vaidilutės để đáp ứng yêu cầu, in ra \(-1\).

Ràng buộc

• \(1\le N\le 2\cdot 10^5\).
• \(2\le M\le 10^9\).
• \(0\le s_i,e_i<M\) với mọi \(1\le i\le N\).
• \(s_i\ne e_i\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(14\) điểm: \(N\le 20\).
2. \(17\) điểm: \(N\le 300\).
3. \(9\) điểm: \(N\le 5000\).
4. \(13\) điểm: với mọi \(1\le i\le N\), \(s_i<e_i\) hoặc \(e_i=0\).
5. \(21\) điểm: khoảng thời gian từ \(s_i\) đến \(e_i\) có cùng độ dài đối với mọi vaidilutė, tính cả trường hợp khoảng thời gian đi qua nửa đêm.
6. \(26\) điểm: không có ràng buộc bổ sung.

Ví dụ

4 100
10 30
30 70
20 40
60 20

3

1 100
30 40

-1

Người ta tin rằng không lâu sau khi cải sang Kitô giáo, Mindaugas, vị vua đầu tiên và duy nhất của Litva, đã ra lệnh xây dựng Nhà thờ chính tòa Vilnius. Công trình gần hoàn thành, chỉ còn sàn nhà cần được lát bằng những viên gạch gốm tráng men có hoa văn.

Sàn nhà thờ là một đa giác trên mặt phẳng hai chiều với hệ tọa độ Descartes. Đa giác có \(N\) đỉnh phân biệt, được đánh số từ \(1\) đến \(N\). Với mỗi \(1\le i\le N\), đỉnh \(i\) nằm tại \((X[i],Y[i])\), trong đó \(X[i]\) và \(Y[i]\) là các số nguyên không âm. Có một cạnh nối đỉnh \(i\) với đỉnh \(i+1\) với mỗi \(1\le i\le N-1\), và một cạnh nối đỉnh \(N\) với đỉnh \(1\). Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Mỗi cạnh của đa giác song song với trục \(x\) hoặc trục \(y\). Ngoài ra, đa giác là đa giác đơn, nghĩa là:

• Tại mỗi đỉnh có đúng hai cạnh gặp nhau.
• Hai cạnh bất kỳ chỉ có thể gặp nhau tại một đỉnh.

Những người thợ có vô hạn viên gạch. Mỗi viên là một hình vuông có cạnh bằng \(2\). Họ muốn lát một phần lớn sàn nhà thờ bằng những viên gạch này. Cụ thể, họ muốn chọn một đường thẳng đứng rồi lát phần sàn nằm bên trái đường thẳng đó. Với mỗi số nguyên \(k\), gọi \(L_k\) là đường thẳng đứng gồm các điểm có hoành độ bằng \(k\). Một cách lát phần sàn bên trái \(L_k\) là một cách đặt một số viên gạch trên mặt phẳng sao cho:

• Mỗi điểm nằm trong miền trong của đa giác và có hoành độ nhỏ hơn \(k\) đều được một viên gạch phủ lên.
• Không có điểm nào nằm ngoài đa giác hoặc có hoành độ lớn hơn \(k\) bị một viên gạch phủ lên.
• Miền trong của các viên gạch không chồng lên nhau.

Hoành độ nhỏ nhất trong các đỉnh của đa giác là \(0\). Gọi \(M\) là hoành độ lớn nhất trong các đỉnh.

Hãy giúp những người thợ tìm số nguyên \(k\) lớn nhất sao cho \(k\le M\) và có thể lát phần sàn nhà thờ bên trái \(L_k\). Lưu ý rằng theo định nghĩa, luôn có thể lát phần sàn bên trái \(L_0\) bằng cách dùng \(0\) viên gạch.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số đỉnh và hoành độ lớn nhất của một đỉnh.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) là tọa độ đỉnh thứ \(i\); đây là các tọa độ được ký hiệu \(X[i]\) và \(Y[i]\) ở trên. Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Dữ liệu ra

In ra giá trị \(k\) lớn nhất sao cho \(k\le M\) và có thể lát phần sàn nhà thờ bên trái \(L_k\).

Ràng buộc

• \(4\le N\le 2\cdot 10^5\).
• \(1\le M\le 10^9\).
• \(0\le y_i\le 10^9\) với mọi \(1\le i\le N\).
• Sàn nhà thờ tạo thành một đa giác đơn có các cạnh song song với các trục tọa độ.
• Giá trị nhỏ nhất trong \(x_1,x_2,\ldots,x_N\) là \(0\), và giá trị lớn nhất là \(M\).

Phân nhóm

1. \(4\) điểm: \(N=4\).
2. \(9\) điểm: \(N\le 6\).
3. \(11\) điểm: \(x_N=0\), \(y_N=0\), đồng thời \(x_i\le x_{i+1}\) và \(y_i\ge y_{i+1}\) với mọi \(1\le i\le N-2\).
4. \(19\) điểm: \(M\le 1000\) và \(y_i\le 1000\) với mọi \(1\le i\le N\).
5. \(22\) điểm: \(y_i\) chẵn với mọi \(1\le i\le N\).
6. \(25\) điểm: \(x_i\) chẵn với mọi \(1\le i\le N\).
7. \(10\) điểm: không có ràng buộc bổ sung.

Ví dụ

14 6
0 1
0 3
2 3
2 4
0 4
0 6
3 6
3 7
4 7
6 7
6 5
3 5
3 2
3 1

2

4 3
0 0
0 3
3 3
3 0

0

18 9
0 2
2 2
2 1
4 1
4 0
9 0
9 2
4 2
4 4
7 4
7 3
9 3
9 6
4 6
4 5
2 5
2 4
0 4

6

Vào thế kỷ XIV, việc xây dựng lâu đài trên đảo Trakai sắp bắt đầu. Công việc đầu tiên của kiến trúc sư trưởng là lên kế hoạch xây dựng bức tường thành chính.

Xây dựng một bức tường có thể bảo vệ lâu đài trước mọi cuộc tấn công là điều khó khăn. Để bảo đảm an toàn cho quân đồn trú, kiến trúc sư trưởng đã giới hạn phần nào các phương án thiết kế.

Vì các cuộc tấn công từ giữa hồ ít có khả năng xảy ra hơn các cuộc tấn công từ bờ gần đó, bức tường không cần tạo thành một vòng khép kín. Thay vào đó, tường sẽ nằm trên một đường thẳng và gồm \(N\) đoạn xếp liên tiếp từ đầu này đến đầu kia, được đánh số từ \(1\) đến \(N\). Việc còn lại là chọn chiều cao cho từng đoạn.

Kiến trúc sư trưởng đã chọn hai chiều cao có thể dùng cho mỗi đoạn. Chiều cao của đoạn thứ \(i\) sẽ là \(a_i\) hoặc \(b_i\). Như vậy, còn \(2^N\) phương án xây tường.

Một lâu đài nằm trên đảo nhỏ giữa hồ cũng có những khó khăn riêng. Trong thời tiết giông bão, lâu đài có thể bị ngập. Khi đó, nước đọng phía trên các đoạn tường nếu ở cả hai phía có những đoạn cao hơn ngăn nước thoát ra.

Với một cách chọn chiều cao các đoạn tường, ta quan tâm đến lượng nước đọng lại trên tường sau một cơn bão lớn. Hình dưới đây minh họa trường hợp chiều cao các đoạn từ trái sang phải là \(4,2,1,8,6,2,7,1,2,3\) và mực nước tại từng vị trí là \(4,4,4,8,7,7,7,3,3,3\).

Một cách hình thức, với mỗi \(i=1,2,\ldots,N\), mực nước tại vị trí \(i\) ít nhất bằng \(h\) khi và chỉ khi tồn tại các số nguyên \(l\) và \(r\) sao cho \(l\le i\le r\) và chiều cao các đoạn tường tại vị trí \(l\) và \(r\) đều ít nhất bằng \(h\). Đặc biệt, mực nước tại các vị trí \(1\) và \(N\) luôn bằng chiều cao đoạn tường tương ứng, và mực nước tại một vị trí bất kỳ luôn lớn hơn hoặc bằng chiều cao đoạn tường ở đó. Lượng nước đọng tại vị trí \(i\) bằng hiệu giữa mực nước và chiều cao đoạn tường. Tổng lượng nước đọng là tổng các lượng nước đọng tại các vị trí \(1,2,\ldots,N\).

Hãy tính tổng lượng nước đọng, cộng trên tất cả \(2^N\) phương án xây tường, và in ra kết quả lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\).

Dòng thứ ba chứa \(N\) số nguyên \(b_1,b_2,\ldots,b_N\).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng lượng nước đọng trên tất cả \(2^N\) phương án xây tường, lấy modulo \(10^9+7\).

Ràng buộc

• \(1\le N\le 5\cdot 10^5\).
• \(1\le a_i,b_i\le 10^9\) và \(a_i\ne b_i\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(8\) điểm: \(N\le 20\).
2. \(17\) điểm: \(N\le 100\) và \(a_i,b_i\le 1000\) với mọi \(1\le i\le N\).
3. \(19\) điểm: \(N\le 10\,000\) và \(a_i,b_i\le 1000\) với mọi \(1\le i\le N\).
4. \(14\) điểm: \(N\le 10\,000\).
5. \(12\) điểm: \(a_i,b_i\le 2\) với mọi \(1\le i\le N\).
6. \(30\) điểm: không có ràng buộc bổ sung.

Ví dụ

4
1 1 1 1
2 2 2 2

6

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

21116