LQDOJ Cup 2024 - Round #2 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	LQDOJ Cup 2024 - Round #2 - Biến đổi dãy ngoặc	100 (p)	0.4s	512M
2	LQDOJ Cup 2024 - Round #2 - Tô màu bóng	100 (p)	1.0s	512M
3	LQDOJ Cup 2024 - Round #2 - Truy vấn thay đổi	100 (p)	3.0s	1G

1. LQDOJ Cup 2024 - Round #2 - Biến đổi dãy ngoặc

Điểm: 100 (p) Thời gian: 0.4s Bộ nhớ: 512M Input: bracket.inp Output: bracket.out

Dãy ngoặc đúng là một dãy chỉ gồm các kí tự mở ngoặc ( và kí tự đóng ngoặc ). Dãy ngoặc đúng là dãy có thể được xây dựng dựa trên nguyên tắc sau:

Một dãy ngoặc rỗng là dãy ngoặc đúng.
Nếu \(A\) là dãy ngoặc đúng thì \((A)\) cũng là một dãy ngoặc đúng.
Nếu \(A\) và \(B\) là dãy ngoặc đúng thì \(AB\) cũng là một dãy ngoặc đúng.

Ví dụ: (())() và () là dãy ngoặc đúng còn ()) không phải là một dãy ngoặc đúng.

Cho một dãy kí tự \(T\) độ dài \(n\). Dãy \(T\) chỉ bao gồm các loại kí tự (, ) và x, kí tự thứ \(i\) \((1 \leq i \leq n)\) của dãy là \(T_{i}\).

Bạn cần thực hiện các thao tác dưới đây để biến \(T\) thành một dãy ngoặc đúng.

Đầu tiên, với mỗi vị trí \(i ~ (1 \leq i \leq n)\) mà \(T_{i} =\) x, bạn phải lựa chọn biến đổi \(T_{i}\) thành một trong hai kí tự là ( hoặc ) tuỳ ý.
Sau đó bạn chọn một đoạn liên tiếp \(\left[ L, R \right]\) \((1 \leq L \leq R \leq n)\) và biến đổi các kí tự của dãy \(T\) trong đoạn. Với mỗi vị trí \(i\) \((L \leq i \leq R)\), nếu \(T_{i} =\) ( thì được biến đổi thành ), nếu \(T_{i} =\) ( thì được biến đổi thành ).

Hỏi có bao nhiêu cách thực hiện các thao tác trên sao cho sau khi thực hiện xong thì dãy \(T\) là một dãy ngoặc đúng. Biết rằng hai cách được xem là khác nhau khi trong hai cách tồn tại một kí tự x được biến đổi thành hai kí tự khác nhau hoặc đoạn \(\left[ L, R \right]\) được chọn trong hai cách là khác nhau.

Input

Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 4000)\).
Dòng thứ hai gồm xâu kí tự \(T ~ (T_i \in \{\) (, ), x \(\})\).

Output

Gồm một số nguyên duy nhất là kết quả của bài toán. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư khi chia kết quả cho \(({10}^9 + 7)\).

Scoring

Subtask \(1\) (\(31\%\) số điểm): \(n \leq 18\).
Subtask \(2\) (\(29\%\) số điểm): \(n \leq 100\).
Subtask \(3\) (\(23\%\) số điểm): Xâu \(T\) chỉ gồm hai loại kí tự là ( và ).
Subtask \(4\) (\(17\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

4
(())

Output

Note

Xâu ban đầu không có kí tự x nào để biến đổi. Ta cần chọn một đoạn \(\left[ L, R \right]\) \((1 \leq L \leq R \leq n)\) thỏa mãn yêu cầu.

Đoạn \(\left[ 2, 3 \right]\) là đoạn duy nhất thỏa mãn. Dãy ngoặc đã cho biến đổi thành ()().

Test 2

Input

2
xx

Output

Note

Ở ví dụ 2, có ba cách thực hiện các thao tác thỏa mãn yêu cầu đề bài:

xx \(\longrightarrow\) )) \(\longrightarrow\) () (chọn đoạn \(\left[ 1, 1 \right]\)).
xx \(\longrightarrow\) (( \(\longrightarrow\) () (chọn đoạn \(\left[ 2, 2 \right]\)).
xx \(\longrightarrow\) )( \(\longrightarrow\) () (chọn đoạn \(\left[ 1, 2 \right]\)).

Test 3

Input

20
(xxxxxxxx(xxxxxxxxxx

Output

2. LQDOJ Cup 2024 - Round #2 - Tô màu bóng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: colorball.inp Output: colorball.out

Cho \(N\) cái túi, mỗi cái túi chứa \(2\) quả bóng màu trắng, túi thứ \(i\) chứa hai quả bóng với các số \(x_{i}, y_{i}\) được viết trên chúng theo thứ tự.

Với mỗi cái túi, bạn hãy tô màu đỏ cho một quả bóng và màu xanh cho quả còn lại. Khi đó, có tất cả \(N\) quả màu đỏ và \(N\) quả màu xanh.

Ta sẽ định nghĩa như sau:

\(R_{\min}\) là số nhỏ nhất được viết trên quả bóng màu đỏ.
\(R_{\max}\) là số lớn nhất được viết trên quả bóng màu đỏ.
\(B_{\min}\) là số nhỏ nhất được viết trên quả bóng màu xanh.
\(B_{\max}\) là số lớn nhất được viết trên quả bóng màu xanh.

Hãy tìm giá trị nhỏ nhất của \((R_{\max} - R_{\min}) \times (B_{\max} - B_{\min})\).

Input

Dòng thứ nhất chứa một số nguyên dương \(N\) (\(N \leq 2 \times 10^5\)) là số lượng túi được cho.
Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa cặp số nguyên \(x_i\), \(y_i\) \((1 \leq x_i, y_i \leq 10^9)\) lần lượt là số trên quả bóng thứ nhất và số trên quả bóng thứ hai của túi thứ \(i\).

Output

Gồm một số nguyên duy nhất là giá trị nhỏ nhất của \((R_{\max} - R_{\min}) \times (B_{\max} - B_{\min})\).

Scoring

Subtask \(1\) (\(29\%\) số điểm): \(N \leq 20\).
Subtask \(2\) (\(27\%\) số điểm): \(N \leq 100\).
Subtask \(3\) (\(23\%\) số điểm): \(N \leq 5000\).
Subtask \(4\) (\(21\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input

Output

Note

Một trong những cách tô màu để tạo ra được giá trị nhỏ nhất của \((R_{\max} - R_{\min}) \times (B_{\max} - B_{\min})\) là:

Túi thứ \(1\): đỏ - xanh
Túi thứ \(2\): đỏ - xanh
Túi thứ \(3\): đỏ - xanh
Túi thứ \(4\): xanh - đỏ
Túi thứ \(5\): đỏ - xanh

\(R_{min} = 1\), \(R_{max} = 5\), \(B_{min} = 3\), \(B_{max} = 9\).

Khi đó \((R_{\max} - R_{\min}) \times (B_{\max} - B_{\min}) = 4 \times 6 = 24\). Không tồn tại cách tô màu khác có giá trị \((R_{\max} - R_{\min}) \times (B_{\max} - B_{\min})\) nhỏ hơn.

3. LQDOJ Cup 2024 - Round #2 - Truy vấn thay đổi

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: cquery.inp Output: cquery.out

Cho mảng \(a\) gồm \(n\) phần tử \(a_1, a_2, ..., a_n\).

Có \(m\) thao tác, thao tác thứ \(i\) được biểu diễn bởi bốn số \(l_i\) \(r_i\) \(x_i\) \(y_i\): Với mọi \(j\) mà \(l_i \leq j \leq r_i\) và \(a_j = x_i\), gán \(a_j = x_i + y_i\).

Bạn cần trả lời \(q\) câu hỏi, câu hỏi thứ \(i\) tương ứng với ba số \(p_i\) \(u_i\) \(v_i\): Hãy cho biết giá trị của phần tử ở vị trí \(p_i\) sau khi thực hiện lần lượt các thao tác từ \(u_i\) đến \(v_i\).

Lưu ý: các câu hỏi độc lập với nhau, tức là trước mỗi câu hỏi, mảng \(a\) trở về trạng thái ban đầu.

Input

Dòng đầu tiên gồm \(2\) số nguyên dương \(n, m\) \((1 \leq n, m \leq 10^5)\) --- độ dài của mảng \(a\) và số lượng thao tác.
Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^5)\)~-- Giá trị ban đầu của mảng.
Dòng thứ \(i\) trong \(m\) dòng tiếp theo gồm bốn số \(l_i, r_i, x_i, y_i\) \((1 \leq l_i \leq r_i \leq m, 1 \leq x_i \leq x_i + y_i \leq 10^5)\) --- Mô tả thao tác thứ \(i\).
Dòng tiếp theo chứa số nguyên duy nhất \(1 \leq q \leq 10^5\) --- số lượng câu hỏi.
Dòng thứ \(i\) trong \(q\) dòng tiếp theo gồm ba số \(p_i, u_i, v_i (1 \leq p_i \leq n, 1 \leq u_i \leq v_i \leq m)\) --- mô tả câu hỏi thứ \(i\).

Output

Gồm \(q\) dòng, dòng thứ \(i\) là câu trả lời cho câu hỏi thứ \(i\).

Scoring

Subtask \(1\) (\(25\%\) số điểm): \(n,m,q \leq 5000\).
Subtask \(2\) (\(20\%\) số điểm): \(l_i = 1, r_i = n\) với mọi thao tác và \(u_i = 1, v_i = m\) với mọi câu hỏi.
Subtask \(3\) (\(23\%\) số điểm): \(n,m \leq 10000, q \leq 10^5\) và \(l_i = 1, r_i = n\) với mọi thao tác.
Subtask \(4\) (\(17\%\) số điểm): \(n,m \leq 5 \times 10^4, a_i \leq 32\) và \(x_i \leq x_i + y_i \leq 32\).
Subtask \(5\) (\(15\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

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

Output

12
8

Note

Có hai câu hỏi:

Câu hỏi đầu tiên, ban đầu mảng \(a = [2, 5, 3, 2, 5, 6, 7, 4, 3, 6]\):
- Sau thao tác đầu tiên, \(a = [2, 5, 3, 2, 45, 6, 7, 4, 3, 6]\).
- Sau thao tác thứ hai, \(a = [2, 9, 3, 2, 45, 6, 7, 4, 3, 6]\).
- Sau thao tác thứ ba, \(a = [2, 9, 3, 2, 45, 6, 7, 4, 3, 6]\).
- Sau thao tác thứ tư, \(a = [2, 9, 3, 2, 45, 6, 8, 4, 3, 6]\).
- Sau thao tác thứ năm, \(a = [2, 12, 3, 2, 45, 6, 8, 4, 3, 6]\).
- Kết quả của câu hỏi này là \(a_2 = 12\).
Ở câu hỏi thứ \(2\), ban đầu mảng \(a = [2, 5, 3, 2, 5, 6, 7, 4, 3, 6]\):
- Thao tác thứ \(1, 2\) và \(5\) không được xét, vì câu hỏi chỉ yêu cầu xét các thao tác từ \(3\) đến \(4\).
- Sau khi thực hiện thao tác thứ ba, \(a = [2, 7, 3, 2, 5, 6, 7, 4, 3, 6]\).
- Sau khi thực hiện thao tác thứ tư, \(a = [2, 8, 3, 2, 5, 6, 8, 4, 3, 6]\).
- Kết quả của câu hỏi này là \(a_2 = 8\).

Test 2

Input

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

Output