LQDOJ CONTEST #13

Khi Majin Buu - một mối nguy hại lớn được giải phong ấn, các chiến binh Z phải chọn ra những chiến binh mạnh nhất để đồng hành cùng bảo vệ Trái Đất.

Họ tìm được \(N\) chiến binh, sức mạnh của người thứ \(i\) \((1 \leq i \leq N)\) là \(p_i\). Bởi vì thời gian là có hạn nên team Z muốn tìm ra một chiến binh có đủ sức mạnh càng sớm càng tốt. Họ có một kĩ thuật ít người biết là Fusion Dance - kĩ thuật cho phép từ hai người có cùng sức mạnh tạo ra được một chiến binh mới có chỉ số sức mạnh bằng tổng sức mạnh của hai người đó, tức là nếu hai người thứ \(i\) và \(j\) \((i \neq j)\) có \(p_i = p_j\) thì hai người này có khả năng hợp thể thành một người mới có chỉ số sức mạnh bằng \((p_i + p_j)\). Người được tạo thành từ phép hợp thể vừa nếu vẫn có thể tiếp tục hợp thể với các người khác miễn là thỏa mãn điều kiện sức mạnh bằng nhau.

Yêu cầu: Với mỗi \(x\) từ \(1\) đến \(N\), hãy giúp team Z tìm ra cách tạo ra chiến binh có chỉ số sức mạnh lớn nhất từ \(x\) chiến binh đầu tiên.

Input

• Dòng đầu tiên gồm một số nguyên dương \(N\) \((1 \leq N \leq 5 \times 10^5)\) là số chiến binh
• Dòng tiếp theo gồm \(N\) số nguyên dương, số thứ \(i\) \((1 \leq i \leq N)\) là \(p_i\) \((1 \leq p_i \leq 10^6)\) - sức mạnh của chiến binh thứ \(i\).

Output

• Một dòng duy nhất gồm \(N\) số nguyên dương, số thứ \(x\) \((1 \leq x \leq N)\) là chỉ số sức mạnh lớn nhất có thể có được từ \(x\) chiến binh đầu tiên

Scoring

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

Example

5
3 2 4 1 2

3 3 4 4 8

Cho một dãy số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^6)\). Hãy đếm số dãy con \(i_1, i_2, \ldots, i_k\) của dãy sao cho

• \(k > 0\),
• \(1 < i_1 < i_2 < \ldots < i_k \leq n\),
• \(a_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k}\),
• \(\gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) = 1\).

Input

Dòng đầu tiên chứa \(T\) \((1 \leq T \leq 3)\) là số bộ dữ liệu.

\(T\) nhóm dòng sau, mỗi nhóm dòng có dạng như sau:

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 3 \times 10^5)\) là số phần tử của dãy.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^6)\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) \((1 \leq i \leq T)\) chứa duy nhất một số nguyên là kết quả của bộ dữ liệu thứ \(i\), trong modulo \((10^9 + 7)\).

Scoring

• Subtask 1 (\(10\%\)): \(n \leq 100, a_i \leq 100\).
• Subtask 2 (\(20\%\)): \(n \leq 3000\).
• Subtask 3 (\(30\%\)): Nếu \(i < j\) và \(a_i \leq a_j\) thì \(\gcd(a_i, a_j) = 1\).
• Subtask 4 (\(40\%\)): Không có ràng buộc gì thêm.

Example

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

1
5
3

Mỗi ngày, có \(n\) em học sinh cần được đưa từ điểm đón xe buýt đến trường. Đường đến trường của các em có thể được coi như một đoạn thẳng từ điểm \(0\) đến điểm \(L\) trên trục số \(O_x\). Có \(n\) em học sinh cần di chuyển từ điểm \(0\) đến điểm \(L\), hiện tại đang có một chiếc xe chở được tối đa \(k\) người tại nơi xuất phát (điểm \(0\)). Vận tốc di chuyển của mỗi em là \(v_1\) (đơn vị độ dài / giây) và vận tốc di chuyển của xe buýt là \(v_2\) (đơn vị độ dài / giây).

Để đến trường sớm nhất có thể thì các em không chỉ đứng đợi tại điểm đón mà có thể tự ý di chuyển (nếu đang không ở trên xe buýt). Biết rằng xe buýt có thể dừng tại bất cứ đâu để đón các em học sinh và coi như thời gian dừng, đón, gia tốc của xe buýt là không đáng kể.

Yêu cầu: Tìm số giây nhỏ nhất có thể để cả \(n\) em di chuyển từ điểm \(0\) đến điểm \(L\). Biết rằng mỗi người chỉ được lên xe tối đa một lần.

Input

• Một dòng duy nhất gồm các số \(n, L, v_1, v_2, k\).

Output

• In ra một số là số giây nhỏ nhất có thể để cả \(n\) em di chuyển từ điểm \(0\) đến điểm \(L\). Đầu ra của thí sinh được coi là đúng nếu sai số với kết quả không quá \(10^{-6}\).

Example

1 5 1 2 1

2.5

2 5 1 2 1

3.5

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n \leq 3\).
• Subtask 2 (\(30\%\) số điểm): \(n \leq 5\).
• Subtask 3 (\(50\%\) số điểm): \(n \leq 3000\).

Cho một đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Đồ thị đảm bảo từ một đỉnh \(u\) có đường đi đến đỉnh \(v\) bất kì.

Gọi \(f(u, v)\) là số lượng cạnh cầu ít nhất trên đường đi từ \(u\) đến \(v\).

Cho \(q\) truy vấn, mỗi truy vấn có dạng: \((u, v, w)\) yêu cầu tìm đỉnh \(x\) sao cho \(f(u, x) + f(v, x) + f(w, x)\) nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa 3 số nguyên dương \(n, m, q\) (\(n, q \leq 10^5, m \leq \min(\frac{n \cdot (n-1)}{2}, 5 \cdot 10^5)\)) lần lượt là số đỉnh, số cạnh của đồ thị, số truy vấn cần xử lí.
• \(m\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u, v\) (\(u, v \leq n\)) mô tả một cạnh của đồ thị.
• \(q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương \(u, v, w\) (\(u, v, w \leq n\)) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, dòng thứ \(i\) chứa một số duy nhất là kết quả của truy vấn thứ \(i\).

Example

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

1
0

Scoring

• Subtask 1 (\(10\%\) số điểm): \(n, q \leq 20\).
• Subtask 2 (\(20\%\) số điểm): \(n \leq 700, m \leq 3000, q \leq 700\).
• Subtask 3 (\(30\%\) số điểm): Đồ thị là cây.
• Subtask 4 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Có \(n\) quả bom nằm trên một đoạn thẳng. Quả bom thứ \(i\) \((1 \leq i \leq n)\) ở vị trí \(x_i\) và có bán kính nổ là \(r_i\). Khi quả bom thứ \(i\) nổ sẽ kích nổ các quả bom \(j\) mà \(x_i - r_i \leq x_j \leq x_i + r_i\).

Để tiến hành việc tháo dỡ \(n\) quả bom này, bạn cần tính toán độ nguy hiểm của mỗi quả bom. Độ nguy hiểm của quả bom thứ \(i\) là \(c_i\) - số quả bom sẽ bị nổ nếu ban đầu
ta chỉ kích nổ quả bom thứ \(i\).

Yêu cầu: Hãy tính \(S = \sum_{i=1}^{n} i \times c_i\). Vì \(S\) có thể rất lớn nên chỉ cần đưa ra số dư trong phép chia \(S\) cho \(({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 5 \times {10}^5)\) là số quả bom.
• \(n\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq n)\) gồm hai số nguyên \(x_i, r_i\) \((-{10}^9 \leq x_i \leq {10}^9, 0 \leq r_i \leq 2 \times {10}^9)\).

Đảm bảo rằng \(x_i \leq x_{i+1}\), \(\forall 1 \leq i < n\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask 1 (\(18\%\) số điểm): \(n \leq 5000\).
• Subtask 2 (\(29\%\) số điểm): \(r_i = 1\), \(\forall 1 \leq i \leq n\).
• Subtask 3 (\(53\%\) số điểm): Không có giới hạn gì thêm.

3
1 1
3 3
10 10

14