Học sinh giỏi lớp 12 của Đà Năng 2024

Viết chương trình nhập vào một số nguyên dương \(N\). Hãy cho biết tổng các số nguyên dương bé hơn \(N\) là bao nhiêu.

Input

• Đọc từ file văn bản TONG.INP một số nguyên dương \(N\).

Output

• Ghi vào file văn bản TONG.OUT số nguyên theo yêu cầu đề bài.

Scoring

• Có \(80\%\) số test tương ứng với \(N \le 10^6\).
• Có \(20\%\) số test tương ứng với \(N \le 10^9\).

Example

5 

10

Tý là một shipper, hằng ngày Tý đến kho hàng để nhận hàng và giao cho khách. Trong kho hàng có \(N\) gói hàng có nhiều màu sắc, các gói hàng có cùng màu sắc sẽ kí hiệu bằng một số giống nhau. Mỗi ngày Tý có thể giao tối đa \(M\) gói hàng, nếu Tý nhận nhiều hơn \(M\) gói hàng anh sẽ không thể giao hết và sẽ bị trừ lương. Tý có thể chọn một màu và quản lí sẽ đưa cho Tý tất cả các gói hàng có màu mà Tý đã chọn. Hãy giúp Tý tìm xem số gói hàng tối đa mà Tý có thể chọn để giao hàng trong ngày hôm đó là bao nhiêu.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\).
• Dòng thứ hai chứa \(N\) số nguyên dương lần lượt là kí hiệu các gói hàng.

Output

• Ghi ra số nguyên theo yêu cầu đề bài.

Scoring

• Có \(40\%\) số test tương ứng với \(N, M \le 10\).
• Có \(60\%\) số test tương ứng với \(N \le 10^5\).

Example

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

4

Có \(n\) viên bi bố trí cách đều theo hàng ngang và được đánh số thứ tự từ \(1\) đến \(n\). Viên bi thứ \(i\) (\(1 \le i \le n\)) có độ đẹp là \(a_i\). Tiến hành thực hiện \(q\) lần một trong hai loại thao tác sau trên dãy các viên bi này:

• 1 i x: thay viên bi tại vị trí thứ \(i\) bằng một viên bi khác có độ đẹp \(x\) (\(1 \le i \le n\), \(-10^9 \le x \le 10^9\)).
• 2 k: dịch chuyển các viên bi sang phải \(k\) vị trí, nếu dãy các viên bi hiện tại là \(a_1, a_2, \dots, a_n\) thì sau khi dịch sẽ là \(a_{n-k+1}, a_{n-k+2}, \dots, a_n, a_1, a_2, \dots, a_{n-k}\) (\(1 \le k \le n\)).

Yêu cầu: sau mỗi lần thực hiện thao tác loại 1, hãy tính tổng độ đẹp của dãy các viên bi đang xuất hiện trên dãy.

Input

• Dòng thứ nhất chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 5\cdot 10^5\)) cách nhau một khoảng trắng.
• Dòng thứ hai chứa các số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)) lần lượt là độ đẹp của các viên bi, các số cách nhau một khoảng trắng.
• \(q\) dòng tiếp theo, mỗi dòng mô tả một thao tác trên, các số cách nhau một khoảng trắng.

Output

• Tương ứng với mỗi phép toán loại 1 ghi ra một số nguyên trên một dòng là tổng độ đẹp của dãy các viên bi xuất hiện trên dãy, thứ tự các kết quả theo đúng thứ tự các phép toán loại 1 trong tệp dữ liệu đầu vào.

Scoring

• Có \(40\%\) số test đầu với \(2 \le n \le 1000\) và chỉ gồm thao tác loại 1.
• Có \(30\%\) số test tiếp theo với \(2 \le n \le 1000\).
• Có \(30\%\) số test còn lại không giới hạn gì thêm.

Example

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

20
12

Thư viện khoa học tổng hợp Đà Nẵng phối hợp với Hội Nhà Báo TP. Đà Nẵng và CLB Nhiếp ảnh TP. Đà Nẵng tổ chức hội Báo Xuân Gíap Thìn năm 2024, triển lãm tài nguyên thông tin và các tác phẩm nhiếp ảnh nghệ thuật chào Xuân. Những tác phẩm nhiếp ảnh nghệ thuật thường là mục tiêu của nhiều tổ chức trộm cắp chuyên nghiệp. Vì thế, ban tổ chức giải quyết bài toán bảo vệ an toàn cho các tác phẩm này. Theo kế hoạch, các tác phẩm trưng bày trong \(n\) giờ, thời điểm bắt đầu cuộc triển lãm được tính bằng \(0\). Có \(m\) vệ sĩ có thể thuê để canh gác tác phẩm. Để đơn giản, các vệ sĩ này được đánh số từ \(1\) đến \(m\). Vệ sĩ \(i\) chấp nhận đứng canh trong khoảng thời gian từ thời điểm \(s_i\) đến thời điểm \(t_i\) (\(0 \le s_i \le t_i \le n\)) với tiền công là \(c_i\) (với \(i=1, 2, \dots, m\)).

Yêu cầu: Hãy giúp ban tổ chức lựa chọn thuê các vệ sĩ nào trong số \(m\) vệ sĩ để bất cứ thời điểm nào diễn ra triển lãm luôn có ít nhất \(1\) vệ sĩ đứng canh, đồng thời tổng chi phí thuê trả cho các vệ sĩ đó là nhỏ nhất.

Input

• Đọc từ tệp văn bản HBAOXUAN.INP có cấu trúc như sau:
  • Dòng đầu tiên ghi hai số nguyên dương \(n\) và \(m\) (\(1 \le n \le m \le 10^5\));
  • Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên không âm \(s_i, t_i, c_i\) (\(0 \le c_i \le 10^9\)). Các số trên một dòng cách nhau bởi một khoảng trắng. Dữ liệu đảm bảo luôn có lời giải.

Output

• Ghi ra tệp văn bản HBAOXUAN.OUT một số nguyên duy nhất là tổng chi phí nhỏ nhất để thuê các vệ sĩ.

Scoring

• Có \(50\%\) số test đầu với \(1 \le n, m \le 10^3\);
• Có \(50\%\) số test còn lại không giới hạn gì thêm.

Example

9 5
0 5 25
1 3 18
3 7 21
4 6 38
7 9 20

66