LQDOJ Contest #1 Mid Autumn 2022 - Div 1

Cho \(n\) đoạn thẳng trên trục tọa độ OX. Đoạn thứ \(i\) là \([l_i, r_i]\) và che phủ các điểm \(j\) với \(l_i \leq j \leq r_i\).

Hãy bỏ đi ít nhất các đoạn sao cho với mọi điểm trên trục OX có tối đa \(k\) đoạn thẳng che phủ nó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq k \leq n \leq 2 \cdot 10^5\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) (\(1 \leq l_i \leq r_i \leq 2 \cdot 10^5\)).

Output

• Dòng đầu tiên chứa số nguyên \(m\) là số lượng đoạn tối thiểu cần loại bỏ.
• Dòng tiếp theo chứa \(m\) số nguyên phân biệt \(p_1, p_2, p_3, \ldots, p_m\) (\(1 \leq p_i \leq n\)) là chỉ số của các đoạn bị loại bỏ theo bất kì thứ tự nào. Nếu có nhiều đáp án, hãy in một đáp án bất kì.

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : \(n \leq 20\).
• Subtask \(2\) (\(25\%\) số điểm) : \(n \leq 5000\).
• Subtask \(3\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.

Example

3 1
1 3 
1 2 
3 3 

1
1

Cho hai số nguyên \(n\) và \(x\). Hãy đếm số lượng dãy \(a\) độ dài \(n\), mỗi phần tử có giá trị trong khoảng \([1, n]\) và hàm sau có giá trị đúng:

binary_search(a, n, x)
    left = 1
    right = n
    while left <= right
        middle = (left + right) / 2
        if a[middle] == x then
            return true

        if a[middle] < x then
            left = middle + 1
        else
            right = middle - 1

    return false

Lưu ý rằng các phần tử của dãy được đánh chỉ số từ \(1\) và phép chia được thực hiện ở phần nguyên (làm tròn xuống).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(x\) (\(1 \leq x \leq n \leq 10 ^ {12}\)).

Output

• Một dòng duy nhất chứa một số nguyên là số lượng dãy \(a\) thỏa mãn sau khi chia lấy dư cho \(10 ^ 9 + 7\).

Scoring

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

Example

3 2

15

Cho một xâu \(s\) chỉ gồm các kí tự a, b, c và d. Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai dạng sau:

• 1 i c: \(i\) là số nguyên \((1 \le i \le |s|)\), \(c\) là kí tự a, b, c hoặc d, có nghĩa là kí tự ở vị trí \(i\) của xâu \(s\) được thay thành kí tự \(c\).
• 2 l r t: \(l\), \(r\) là số nguyên \((1 \le l \le r \le |s|)\), \(t\) là một xâu chỉ chứa các kí tự a, b, c và d \((1 \le |t| \le 10)\), có nghĩa là nếu viết tiền tố của xâu \(ttt\dots\) (xâu chứa vô số xâu \(t\) được viết liên tiếp nhau) dưới xâu \(s\) từ vị trí \(l\) đến \(r\) thì số lượng vị trí mà kí tự của xâu \(s\) trùng với kí tự được viết dưới nó là bao nhiêu?

Input

• Dòng đầu tiên chứa xâu \(s\) \((1 \le |s| \le 10^5)\).
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \le q \le 10^5)\).
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa một trong hai dạng 1 i c hoặc 2 l r t.

Output

• Với mỗi truy vấn dạng 2 l r t, in ra một số nguyên là kết quả.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le |s|, q \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): Tất cả các truy vấn dạng 2 l r t đều có \(|t| = 1\).
• Subtask \(3\) (\(50\%\) số điểm): Không ràng buộc gì thêm.

Example

abcdcdd
4
2 2 5 bc
2 3 7 cdc
1 5 a
2 3 7 cdc 

3
4
3

Trong mùa trung thu này, có một trò chơi được rất nhiều bạn trẻ ưa chuộng, trong đó có Jessie - một cao thủ gaming. Đó là trò chơi giải cứu công chúa. Với quyết tâm trở thành vua trò chơi thứ hai (sau Mutō Yūgi), Jessie quyết định sẽ đạt thành tích tốt nhất có thể trong trò chơi này. Trò chơi gồm \(n\) màn chơi và \(m\) cánh cổng. Cánh cổng thứ \(i\) đi từ màn \(v_{i}\) đến màn \(t_{i}\) \((v_{i} < t_{i})\) và được canh giữ bởi một con boss với điểm sức mạnh là \(l_{i}\). Công chúa bị nhốt tại một tòa lâu đài ở màn \(n\), để phá được tòa lâu đài và cứu công chúa ra, Jessie cần có điểm sức mạnh ít nhất là \(D\).

Jessie sẽ bắt đầu chơi từ màn \(1\) với điểm sức mạnh có sẵn là \(p\). Để vượt qua một cánh cổng đi từ màn \(v_{x}\) đến màn \(t_{x}\), Jessie buộc phải đối đầu với con boss canh giữ cánh cổng đó. Nếu điểm sức mạnh hiện tại của Jessie lớn hơn điểm của boss, Jessie sẽ đánh bại con boss và được tăng thêm \(\left\lfloor \dfrac{l_{x}}{2} \right\rfloor\) điểm sức mạnh (phép chia làm tròn xuống). Ngược lại, Jessie sẽ phải hiến tế và mất đi một nửa điểm sức mạnh của mình (phép chia làm tròn xuống) để con boss mở cánh cổng cho cô qua.

Bạn hãy giúp Jessie xác định xem liệu cô có thể giải cứu được công chúa không. Nếu được, Jessie cần biết điểm sức mạnh tối đa mà cô có thể đạt được là bao nhiêu.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \leq t \leq 1000)\) thể hiện số test. Mỗi test có dạng:
• Dòng đầu tiên chứa bốn số nguyên \(n, m, p, D\) \((2 \leq n \leq 10^{6}, 1 \leq m \leq 2 \times n, 0 \leq p, D \leq 10^{9})\).
• \(m\) dòng sau, dòng thứ \(i\) chứa ba số nguyên \(l_{i}, v_{i}, t_{i}\) \((0 \leq l_{i} \leq 10^{9}, 1 \leq v_{i} < t_{i} \leq 10^{6})\).
• Tổng \(n\) trong tất cả các test không vượt quá \(10^{6}\).

Output

• Với mỗi test, in ra Impossible nếu không thể giải cứu công chúa. Ngược lại, in ra điểm sức mạnh tối đa đạt được.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(15\%\) số điểm): Có \(n - 1\) cánh cổng, cánh cổng thứ \(i\) cho phép đi đến màn chơi \(i + 1\) sau khi hoàn thành màn chơi \(i\).
• Subtask \(3\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 1 10 10
9 1 2
2 1 10 10
10 1 2
5 6 10 24
7 1 2
10 2 3
12 2 5
3 1 3
11 3 4
17 3 5

14
Impossible
26

Thành phố X là một thành phố rộng lớn được chia làm \(n\) phân khu. Các phân khu được nối với nhau bởi \(n - 1\) con đường hai chiều, mỗi con đường nối trực tiếp giữa hai phân khu nào đấy sao cho đảm bảo luôn tồn tại đường đi giữa hai phân khu bất kỳ.

Là thành phố lớn nhất nhì trong cả nước, mật độ phương tiện giao thông ở đây là vô cùng khổng lồ, dẫn đến gánh nặng rất lớn về chi phí bảo trì và sửa chữa và bảo trì cơ sở hạ tầng. Do đó, chính quyền thành phố đã cho xây dựng ở mỗi phân khu một trạm kiểm soát.

Khi một phương tiện giao thông di chuyển tới một phân khu, phương tiện bắt buộc phải đi qua trạm kiểm soát này. Mỗi trạm kiểm soát sẽ có một mức giới hạn tải trọng, trạm kiểm soát ở phân khu \(i\) sẽ có mức giới hạn là \(l_{i}\) kg. Giả sử một phương tiện đi qua và có tải trọng lớn hơn giới hạn tải trọng của trạm kiểm soát, chủ phương tiện phải trả cho trạm kiểm soát đó khoảng phạt là \(1\) đồng cho mỗi kg vượt giới hạn. Cụ thể hơn, nếu một phương tiện có tải trọng \(w\) đi qua trạm kiểm soát ở phân khu \(i\), chủ phương tiện đó phải trả cho trạm kiểm soát đó \(\max(w - l_{i}, 0)\) đồng.

Bạn biết được ngày hôm nay đã có \(m\) phương tiện di chuyển, phương tiện \(i\) di chuyển từ phân khu \(s_{i}\) tới phân khu \(t_{i}\) với trọng tải \(w_{i}\) (Lưu ý rằng phương tiện cũng phải đi qua trạm kiểm soát của điểm xuất phát và đích đến). Với mỗi trạm kiểm soát, hãy cho biết sau ngày hôm nay trạm kiểm soát đó đã thu được bao nhiêu tiền.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 3 \times 10^{5})\).
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i}, v_{i} \leq n)\) có nghĩa là có đường nối trực tiếp giữa phân khu \(u_{i}\) và \(v_{i}\).
• Dòng tiếp theo chứa \(n\) số nguyên \(l_{i}\) \((0 \leq l_{i} \leq 10^{9})\).
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(s_{i}, t_{i}\) và \(w_{i}\) \((1 \leq s_{i}, t_{i} \leq n, 1 \leq w_{i} \leq 10^{9})\).

Output

• Một dòng duy nhất chứa \(n\) số nguyên, số thứ \(i\) là số tiền mà trạm kiểm soát ở phân khu \(i\) thu được sau ngày hôm nay.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m \leq 100\).
• Subtask \(2\) (\(25\%\) số điểm): Thành phố có dạng đường thẳng.
• Subtask \(3\) (\(25\%\) số điểm): \(l_{i} = 0\) với mọi \(1 \leq i \leq n\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

2 1 0 0 

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

0 5 7 5 0 5 2 2

Tết Trung Thu rước đèn đi chơi
Em rước đèn đi khắp phố phường
Lòng vui sướng với đèn trong tay
Em múa ca trong ánh trăng rằm
Đèn ông sao với đèn cá chép
Đèn thiên nga với đèn bướm bướm
Em rước đèn này đến cung trăng
Đèn xanh lơ với đèn tím tím
Đèn xanh lam với đèn trắng trắng
Trong ánh đèn rực rỡ muôn màu.

Hòa cùng không khí vui nhộn của ngày Tết Trung Thu, Tuân cùng các bạn trong xóm sẽ tụ họp lại và đi rước đèn ông sao từ đầu làng đến cuối làng như mọi năm.

Nhưng năm nay lạ lắm, đường làng không còn là một đường thẳng như mọi khi. Đường làng đã biến thành một bảng hình chữ nhật kích thước \(3 \times m\) và có \(n\) chướng ngại vật xuất hiện trên đường.

Mặc dù tuổi còn nhỏ nhưng não của Tuân khá to, Tuân quyết định dẫn đầu đoàn rước tìm đường vượt qua các chướng ngại vật và đi đến cuối làng. Thấy vậy là quá dễ nên Tuân còn có ý tưởng táo bạo hơn đó chính là đếm số cách đi từ đầu làng đến cuối làng sao cho Tuân và các bạn sẽ xuất phát ở ô \((2,1)\) và kết thúc ở ô \((2,m)\). Với mỗi ô \((i, j)\), Tuân chỉ có thể di chuyển đến ô:

• \((i - 1, j + 1)\) nếu \(i>1\)
• \((i, j + 1)\)
• \((i + 1, j + 1)\) nếu \(i<3\)

Có \(n\) chướng ngại vật trên đường sẽ được biểu diễn bởi bộ ba số nguyên \(a_i\), \(l_i\) và \(r_i\) và Tuân bị cấm không được di chuyển vào các ô \((a_i, j)\) với \(l_i \le j \le r_i\) (Lưu ý rằng các chướng ngại vật có thể chồng lên nhau).

Thấy số cách có vẻ rất lớn nên Tuân rất cần bạn giúp đỡ và tìm ra phần dư của nó khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(0 \leq n \leq 10 ^ 4\), \(1 \leq m \leq 10 ^ {18}\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(a_i\), \(l_i\) và \(r_i\) (\(1 \leq a_i \leq 3\), \(2 \leq l_i \leq r_i \leq m - 1\)).

Output

• In ra một số nguyên duy nhất là số cách đi thỏa mãn khi sau khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n = 0\) và \(m \le 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): \(m \le 10^6\).
• Subtask \(3\) (\(20\%\) số điểm): \(n = 0\).
• Subtask \(4\) (\(20\%\) số điểm): \(r_i < l_{i+1}\) với mọi \(1 \leq i \leq n - 1\).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.

Example

2 5  
1 3 4  
2 2 3

2