# ÔN LUYỆN THI QUỐC GIA - SỐ 5

**Lưu ý:** Lần này tất cả các bài đều được nhập xuất ở dạng `standard input | standard output`
**Ngôn ngữ cho phép**: `C/C++`,`Python`,`Assembly`

---

## Bài 1. GIẤY DÁN TƯỜNG
---
:::info
:::spoiler Thông số bài tập
Author: **leduclv**
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1024MB
Điểm: **100**
:::
Có một bức tường cao $M$ mét, dài $N$ mét được chia thành $M * N$ ô vuông kích thước $1 * 1$ mét. Bức tường được dán giấy nhưng qua nhiều năm sử dụng một số bị ngấm nước và hỏng. Người ta quyết định bỏ đi những ô bị hỏng & dán lại.
Người ta mua về một cuộn giấy loại có bản rộng $1$ mét và độ dài được xem là **không hạn chế**. Do chiều hoa văn của giấy dán nên chỉ có thể nên dán theo chiều đứng. Để đỡ mất công, nếu có một vùng $K$ ô liên tiếp theo chiều thẳng đứng cùng phải thay thế thì người ta sẽ cắt một băng giấy dài $K$ mét và dán một lần. Không được dán lê những ô không hỏng.
**Yêu cầu:** Hãy lập chương trình tính số lần cắt (mỗi lần cắt lấy ra được một mảnh) để dán được hết chỗ hỏng trên tường.
**Dữ liệu:**
- Dòng đầu gồm $2$ số tự nhiên $M,N$ cách nhau một dấu cách tương ứng là chiều cao và chiều dài của bức tường. $(4<M<51 ; 0<N<101)$.
- Tiếp theo là $M$ dòng, dòng thứ $i$ trong $M$ dòng đó thể hiện tình trạng cửa hàng ô chữ thứ $i$ tính từ trên xuống. Bít thứ $j$ là `1` nếu ô thứ $j$ trong hàng đó không bị hỏng và bằng `0` nếu ô đó bị hỏng.

**Kết quả:** Ghi ra một số duy nhất là số lần cắt.
(Các bạn có thể vẽ ra để hiểu ra vấn đề)

**Sample Input**

6 12
011101101110
010100101010
010100100011
010111100010
011101101010
110101101110

**Sample Output**

11

---
## Bài 2. AQUERY
---
:::info
:::spoiler Thông số bài tập
Author: **kimjongun**
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB
Điểm: **200**
:::
Cho một dãy $A$ gồm $N$ phần tử. Ban đầu, giá trị của các phần tử đều bằng $0$. Có $Q$ truy vấn, truy vấn thứ $i$ được mô tả bởi hai số nguyên $r_i$ và $p_i$, yêu cầu thực hiện $p_i$ lần các thao tác sau:
- Chọn phần tử có giá trị nhỏ nhất trong các phần tử có vị trí từ $1$ đến $r_i$. Nếu có nhiều phần tử có cùng giá trị nhỏ nhất, chọn phần tử có vị trí nhỏ nhất trong số chúng.
- Tăng giá trị của phần tử được chọn thêm $1$.

Hãy cho biết giá trị các phần tử trong dãy $A$ sau khi thực hiện $Q$ truy vấn trên.
**Dữ liệu:**
- Dòng đầu tiên gồm hai số nguyên $N, Q$ $(1 ≤ N, Q ≤ 10^5)$ - số phần tử của dãy $A$ và số truy vấn cần thực hiện.
- $Q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $r_i$ và $p_i$ $(1 ≤ r_i ≤ N, 1 ≤ p_i ≤ 9 ∗ 10^8)$ - mô tả truy vấn thứ $i$.

**Kết quả:**
- In ra $N$ số nguyên lần lượt là giá trị các phần tử trong dãy $A$ sau khi thực hiện $Q$ truy vấn.

**Sample Input**

8 3
3 11
8 7
6 3

**Sample Output**

4 4 3 3 3 2 1 1

**Sample Input**

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

**Sample Output**

2 2 1 0 0

:::info
:::spoiler **Giải thích ví dụ thứ nhất**
- Sau khi thực hiện truy vấn $1$, dãy $A$ trở thành: `[4, 4, 3, 0, 0, 0, 0, 0]`
- Sau khi thực hiện truy vấn $2$, dãy $A$ trở thành: `[4, 4, 3, 2, 2, 1, 1, 1]`
- Sau khi thực hiện truy vấn $3$, dãy $A$ trở thành: `[4, 4, 3, 3, 3, 2, 1, 1]`
:::

:::info
:::spoiler **Giải thích ví dụ thứ hai**
- Sau khi thực hiện truy vấn 1, dãy A trở thành: `[1, 0, 0, 0, 0]`
- Sau khi thực hiện truy vấn 2, dãy A trở thành: `[1, 1, 0, 0, 0]`
- Sau khi thực hiện truy vấn 3, dãy A trở thành: `[1, 1, 1, 0, 0]`
- Sau khi thực hiện truy vấn 4, dãy A trở thành: `[2, 1, 1, 0, 0]`
- Sau khi thực hiện truy vấn 5, dãy A trở thành: `[2, 2, 1, 0, 0]`
:::
---
## Bài 3. CONNECT
---
:::info
:::spoiler Thông số bài tập
Author: **bangtanisdabest**
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB
Điểm: **300**
:::
Trên trục tọa độ $Ox$, có $N$ máy tính và $N$ ổ cấm điện. Máy tính thứ $i$ có tọa độ là $A_i$, ổ cắm điện thứ $i$ có tọa độ $B_i$. $2N$ điểm này có tọa độ đôi một khác nhau.
Người ta muốn tìm cách kết nối từng máy tính với một ổ cắm điện, sử dụng một sợi dây. Nếu nối
máy tính $i$ với ổ cắm $j$ thì độ dài sợi dây cần dùng là $|Ai − Bj|$. Mỗi ổ cắm điện chỉ được nối với một máy tính.
Hãy đếm xem có bao nhiêu cách kết nối máy tính với ổ cắm sao cho tổng độ dài dây cần dùng là ít nhất có thể. Vì đáp án có thể rất lớn nên hãy in số cách sau khi chia lấy dư cho $10^9 + 7$.
**Dữ liệu:**
- Dòng đầu tiên gồm số nguyên $N (1 ≤ N ≤ 10^5)$ - số máy tính và ổ cắm điện.
- Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, ..., A_N (0 ≤ A_i ≤ 10^9)$ - tọa độ của $N$ máy tính.
- Dòng thứ ba gồm $N$ số nguyên $B_1, B_2, ..., B_N (0 ≤ B_i ≤ 10^9)$ - tọa độ của $N$ ổ cắm.

**Kết quả:**
- In ra số cách nối sau khi chia lấy dư cho $10^9 + 7$

**Sample Input**

2
50 60
70 80

**Sample Output**

2

**Sample Input**

3
50 30 10
20 60 40

**Sample Output**

1

:::info
:::spoiler **Giải thích**
- Trong ví dụ thứ nhất, có hai cách nối với tổng chi phí nhỏ nhất:
$-50-70,60-80$
$– 50 − 80, 60 − 70$
- Ở ví dụ thứ hai,cách nối duy nhất với tổng chi phí nhỏ nhất $(30)$ là: $50 − 60, 30 − 40, 10 − 20$.
:::

---
Chúc các bạn làm bài tốt.