TRẠI HÈ PHƯƠNG NAM LẦN THỨ VII Problems

Từ an toàn

Điểm: 7 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Phương là một người thích sự độc đáo, anh ta rất không thích sự lặp lại, ngay cả khi nó xuất hiện trong các cuộc trò chuyện hàng ngày. Phương cảm thấy khó chịu khi phải dùng các từ có quá nhiều chữ cái lặp lại. Cụ thể với một từ $W$ bất kì, cậu định nghĩa $F(W)$ là độ khó chịu của từ đó. $F(W)$ được tính bằng tổng của bình phương số lần xuất hiện trong $W$ với mỗi chữ cái. Ví dụ với $W$ = “hello” có $2$ chữ cái ‘l’, $1$ chữ cái ‘h’, $1$ chữ cái ‘e’ và $1$ chữ cái ‘o’ có độ khó chịu là $F(W) = 2^2 + 1^2 + 1^2 + 1^2 = 7.$
Phương chỉ muốn sử dụng những từ an toàn, nghĩa là những từ có độ khó chịu nhỏ hơn hoặc bằng một số nguyên $K$ cho trước.
Yêu cầu: Phương có một xâu $S$ độ dài $N$ chỉ gồm chữ cái in thường (từ ‘a’ đến ‘z’). Hãy giúp Phương đếm số lượng xâu con là từ an toàn của $S$.

Nhắc lại, một xâu con của một xâu $S$ cho trước là một xâu thu được khi xóa một số ký tự liên tiếp nhau (hoặc không xóa) ở đầu xâu $S$ và một số ký tự liên tiếp nhau (hoặc không xóa) ở cuối xâu $S$. Ví dụ “olp” hay “psou” là xâu con của “olpsouth” trong khi “suh” thì không. Hai xâu con được coi là khác nhau nếu số lượng ký tự bị xóa ở đầu xâu khác nhau hoặc số lượng ký tự bị xóa ở cuối xâu khác nhau.

Input

Dòng thứ nhất chứa hai số nguyên $N$ và $K$ lần lượt là độ dài của xâu $S$ và giới hạn của từ an toàn $(1 \le N \le 2 000 000, 1 \le K \le 10^{18})$.
Dòng thứ hai chứa một xâu độ dài $N$ chỉ gồm các chữ cái in thường mô tả xâu $S$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Một số nguyên duy nhất là số lượng xâu con của $S$ là từ an toàn.

Scoring

Subtask $1$ ($20\%$ số test): $n \le 100$.
Subtask $2$ ($20\%$ số test): $n \le 1000$.
Subtask $3$ ($20\%$ số test): $n \le 10000$.
Subtask $4$ ($20\%$ số test): $n \le 200000$.
Subtask $5$ ($20\%$ số test): Không có ràng buộc gì thêm.

Example

Test 1

Input

4 5
abaa

Output

Note

Trong ví dụ đầu tiên, các xâu con là từ an toàn lần lượt là: “a”, “a”, “a”, “b”, “ab”, “ba”, “aa”, “aba”, “baa”.
Từ “abaa” không phải là từ an toàn vì trong đó có 3 chữ cái “a” và 1 chữ cái “b” nên có độ khó chịu là: $f($“abaa”$) = 32 + 12 = 10 > K = 5$.

Test 2

Input

9 10
aabbabaaa

Output

Test 3

Input

12 12
mmississippi

Output

Ước số

Nộp bài

Điểm: 7 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Các ước số tự nhiên có vai trò quan trọng trong nhiều thuật toán mã hóa, chẳng hạn như RSA, một thuật toán mã hóa công khai phổ biến. Việc tạo ra dãy các ước số của một tập hợp số tự nhiên có thể giúp hiểu được cách các ước số phân phối và ảnh hưởng đến tính bảo mật của mã hóa. Là một người yêu thích môn mật mã, Nam quan sát đặc điểm các ước số của một tập hợp số tự nhiên thông qua bài toán sau. Nam có một dãy số $A$ gồm $N$ phần tử, mỗi phần tử là một số tự nhiên khác 0. Gọi $D$ là dãy các phần tử có giá trị không giảm gồm tất cả các ước số tự nhiên, không nhất thiết phải phân biệt của các phần tử của $A$. Nam chuẩn bị dãy $P$ gồm $Q$ số tự nhiên khác 0, mỗi số biểu thị một vị trí trong dãy $D$. Do dãy $D$ chưa được cho trước mà phải tính toán thông qua các giá trị trong dãy $A$ và $N$, Nam mong muốn xác định nhanh từng giá trị phần tử trong dãy $D$ tương ứng với mỗi phần tử thuộc dãy $P$. Ví dụ, với $N = 4$, $A = (10, 2, 5, 2)$ và $P = (5, 1, 10)$, ta có dãy $D = (1, 1, 1, 1, 2, 2, 2, 5, 5, 10)$ và các giá trị phần tử trong dãy $D$ tương ứng với mỗi phần tử thuộc dãy $P$ là $(2, 1, 10)$.
Yêu cầu: Hãy giúp Nam xác định từng phần tử trong dãy $D$ tương ứng với với mỗi phần tử trong
dãy $P$.

Input

Dòng đầu tiên chứa hai số nguyên dương $N$ và $Q$ lần lượt là số lượng phần tử dãy $A$ và số
lượng phần tử dãy $P$ $(1 \le N \le 10^6; 1 \le Q \le 10^5)$.
Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots , A_N$ mô tả dãy $A$ $(1 \le A_i \le 10^6).
Dòng thứ ba chứa $Q$ số nguyên dương $P_1, P_2, \dots , P_Q$ mô tả dãy $P$ $(1 \le P_i \le |D|$, với $|D|$ là số lượng phần tử dãy $D)$.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra duy nhất một dòng gồm $Q$ số nguyên, cách nhau bởi dấu cách, là các phần tử trong dãy $D$ tương ứng với các phần tử trong dãy $P$.

Scoring

Subtask $1$ ($25\%$ số test): $N0, Q \le 1000; A_i \le 1000$ với mọi $1 \le i \le N; P_i \le 1000$ với mọi $1 \le i \le Q$.
Subtask $2$ ($25\%$ số test): $A_i$ là số nguyên tố với mọi $1 \le i \le N$.
Subtask $3$ ($20\%$ số test): $n \le 10000; P_i \le 2 \cdot 10^6$ với mọi $1 \le i \le Q$.
Subtask $4$ ($20\%$ số test): $P_i \le 2 \cdot 10^6$ với mọi $1 \le i \le Q$.
Subtask $5$ ($10\%$ số test): Không có ràng buộc gì thêm.

Example

Test 1

Input

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

Output

1 1 1 1 2 2 2 5 5 10

Note

$N = 4$
$Q = 10$
$A = (10, 2, 5, 2)$
$D = (1, 1, 1, 1, 2, 2, 2, 5, 5, 10)$

Test 2

Input

4 5
10 2 5 2
5 1 10 9 8

Output

2 1 10 5 5

Note

$N = 4$
$Q = 5$
$A = (10, 2, 5, 2)$
$D = (2, 1, 10, 5, 5)$

Phương Nam

Nộp bài

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Phương Nam có $N$ khu vực hành chính, được đánh số từ $1$ đến $N$, được kết nối liên thông bởi $N −1$ con đường tạo thành dạng cây trong lý thuyết đồ thị. Mỗi khu vực tương ứng với một đỉnh của cây, mỗi con đường tương ứng với một cạnh của cây. Nhắc lại, cây là một đồ thị vô hướng, liên thông và không có chu trình. Mỗi khu vực người ta gán cho một giá trị biểu thị mức độ phát triển khu vực đó, khu vực thứ $i$ có có giá trị $A_i$.

Nhằm quy hoạch phát triển các khu vực một cách hiệu quả, người ta đánh giá một cụm $S$ các khu vực liên thông nhau thông qua các con đường nối giữa chúng trong cụm đó bởi một độ hiệu quả. Giá trị độ hiệu quả này được tính bằng hiệu của giá trị lớn nhất trong số các giá trị khu vực thuộc $S$ và giá trị nhỏ nhất trong số các giá trị khu vực thuộc $S$. Nói cách khác, với một cụm liên thông $S$, giá trị của $S$ là $max_{u \in S} A_u − min_{u \in S} A_u$.

Người ta muốn chia toàn bộ $N$ khu vực thành các cụm khu vực riêng biệt, mỗi cụm bao gồm một
hoặc nhiều khu vực liên thông nhau bởi các con đường nối các khu vực trong cụm đó và đánh giá
độ hiệu quả trên mỗi cụm. Tổng độ hiệu quả của một cách chia như vậy được tính bằng tổng giá
trị của các cụm liên thông trong cách chia đó.

Yêu cầu: Hãy tìm cách chia toàn bộ $N$ khu vực thành các cụm có tổng độ hiệu quả lớn nhất.

Input

Dòng thứ nhất chứa một số nguyên $N$ $(1 \le N \le 3 \cdot 10^5)$ là số lượng khu vực ở Phương Nam.
Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots , A_N$ $(1 \le A_i \le 10^9)$ mô tả độ phát triển của khu vực tương ứng.
Dòng thứ $i$ trong $$ dòng tiếp theo chứa hai số nguyên $u_i, v_i$ $(1 \le u_i, v_i \le N)$ mô tả một con đường nối hai khu vực $u_i$ và $v_i$. Dữ liệu đảm bảo các con đường này tạo thành một cây.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra một số nguyên duy nhất là tổng độ hiệu quả lớn nhất tìm được.

Scoring

Subtask $1$ ($30\%$ số test): $N \le 20$.
Subtask $2$ ($30\%$ số test): $N \le 2000$ và tất cả các đỉnh có bậc không quá $2$.
Subtask $3$ ($20\%$ số test): Tất cả các đỉnh có bậc không quá $2$.
Subtask $4$ ($20\%$ số test): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

Note

Mỗi đỉnh tượng trưng cho một khu vực bao gồm hai số, số thứ nhất là chỉ số của khu vực, số thứ hai là giá trị của khu vực đó. Các đường đi được mô tả bằng các cạnh nỗi giữa các đỉnh.

Test 2

Input

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

Output

Note

Mỗi đỉnh tượng trưng cho một khu vực bao gồm hai số, số thứ nhất là chỉ số của khu vực, số thứ hai là giá trị của khu vực đó. Các đường đi được mô tả bằng các cạnh nỗi giữa các đỉnh.