USACO 2023 - US Open - Hạng Bạc

Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường

Nông dân John có \(N\) \((1 \le N \le {1.5 \times 10^5})\) con bò được đánh số từ \(1\) đến \(N\), con bò \(i\) sản xuất được \(a_i\) \((1 \le a_i \le 10^8, a_i \in \mathbb{Z})\) đơn vị sữa mỗi phút.

Mỗi sáng thức dậy, John bắt đầu với các con bò đang bị xích vào máy vắt sữa trong chuồng, bác ta sẽ thả từng con một ra ngoài để tập thể dục buổi sáng. Con bò đầu tiên được thả sau \(1\) phút vắt sữa, con bò thứ \(2\) được thả sau \(2\) phút vắt sữa, ... Hay nói cách khác, con bò thứ \(i\) được thả sau \(i\) phút vắt sữa, giả sử con bò này được đánh là \(x\) thì sẽ sản xuất được \(a_x \times i\) đơn vị sữa. Gọi \(T\) là lượng sữa lớn nhất mà bác John thu thập được nếu thả các con bò ra theo thứ tự tối ưu.

Bác ta tò mò liệu \(T\) sẽ thay đổi thế nào các một số con bò sản xuất ra lượng sữa khác đi. Có \(Q\) \((1 \le Q \le {1.5 \times 10^5})\) truy vấn, gồm \(2\) số nguyên \(i\) và \(j\), với mỗi truy vấn hãy tính toán \(T\) sẽ thay đổi thế nào nếu \(a_i\) được đặt thành \(j\) \((1 \le j \le 10^8)\). Các truy vấn là độc lập, nghĩa là các truy vấn đều chỉ áp dụng lên trạng thái ban đầu của dãy \(a\).

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là \(N\) số \(a_1, a_2, ..., a_N\).
• Dòng thứ ba là số \(Q\).
• Trong \(Q\) dòng tiếp theo là \(2\) số nguyên thể hiện mỗi truy vấn.

Output

• In ra giá trị mới của \(T\) cho mỗi truy vấn trên \(Q\) dòng.

Scoring

• Subtask \(1\): \(max(N, Q) \le 1000\).
• Subtask \(2\): Không có ràng buộc gì thêm.

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

55
81
98

Note: Giới hạn thời gian cho Python là 15s. Các ngôn ngữ lập trình khác là 2s.

Trong các chuồng của nông dân John, đều có \(1\) đội gồm \(C\) chú bò \((1 \le C \le 18)\) để tham gia vào ngày hội thao. Chủng tộc của mỗi chú bò đều là Guernsey hoặc Holstein.

Độ khác biệt giữa hai đội là số lượng vị trí \(i\) \((1 \le i \le C)\) mà chủng bò ở vị trí này của hai đội là khác nhau. Với mỗi đội, hãy tìm độ khác biệt lớn nhất giữa đội đó với các đội còn lại.

Input

• Dòng đầu tiên gồm \(2\) số \(N\) và \(C\).
• \(N\) dòng tiếp theo chứa một xâu kí tự độ dài \(C\) chỉ bao gồm 'G' và 'H'.

Output

• Gồm \(N\) dòng, dòng thứ \(i\) là độ khác biệt lớn nhất của đội \(i\) với các đội còn lại.

Scoring

• Subtask \(1\): \(C = 10\).
• Subtask \(2\): \(\forall i\) độ khác biệt lớn nhất giữa đội \(i\) với các đội còn lại không nhỏ hơn \(C - 3\)
• Subtask \(3\): Không ràng buộc gì thêm.

5 3
GHGGH
GHHHH
HGHHG

5
3
5

Note: Giới hạn thời gian của bài này là 4s, gấp đôi so với thông thường

Pareidolia là một hội chứng mà mắt bạn có xu hướng nhìn thấy những thứ quen thuộc trong ảnh mà thậm chí không tồn tại (ví dụ như thấy một gương mặt trên đám mây). Nông dân John, một người với niềm yêu thương những chú bò của mình, thường xuyên thấy những thứ liên quan đến bò trong mọi vật dụng. Ví dụ, nếu như bác John thấy xâu "bqessiyexbesszieb", đôi mắt của bác sẽ tự động bỏ đi một số kí tự và nhầm lẫn thành "bessiexbessieb" - một xâu gồm \(2\) xâu con liên tiếp "bessie" (tên một cô bò mà bác rất yêu quý).

Với một xâu \(s\), ta gọi \(B(s)\) là số lượng xâu con liên tiếp "bessie" nhiều nhất có thể đạt được từ xâu \(s\) nếu xoá đi \(0\) hoặc nhiều kí tự trong xâu \(s\). Trong ví dụ trên, \(B(\)"bqessiyexbesszieb"\() = 2\).

Tính toán \(B(s)\) rất là thú vị, vì vậy bác John cho bạn một thử thách: Bạn được cho một xâu \(t\) độ dài không quá \(3 \times 10^5\) chỉ bao gồm các chữ cái in thường, hãy tính tổng \(B(s)\) cho mọi xâu con liên tiếp \(s\) của xâu \(t\).

Input

• Gồm một dòng duy nhất chứa xâu \(t\).

Output

• Gồm một dòng duy nhất chứa tổng các \(B(s)\).

Scoring

• Subtask \(1\): xâu \(t\) có độ dài không quá \(5000\).
• Subtask \(2\): Không có thêm ràng buộc.

abcdefghssijebessie

28