Độ khó: Khó (4/4 điểm)

Cho bốn số nguyên ~N, K, X, Y~ và dãy số từ ~1~ tới ~N~. Mỗi lượt thực hiện hai thao tác theo thứ tự sau:

• Bước 1: Lấy các phần tử nằm ở vị trí là số chính phương trong dãy và chuyển tới bên trái dãy;
• Bước 2: Lấy các phần tử nằm ở vị trí là số chính phương trong dãy và chuyển tới bên phải dãy.

Ví dụ: Với ~N = 6~ và dãy số ban đầu là ~[1,2,3,4,5,6]~, lượt ~1~ sẽ thực hiện các bước sau:

• Bước 1: Dồn số ở vị trí ~1~ và vị trí ~4~ sang bên trái, dãy số ~[\mathbf{1}, 2, 3, \mathbf{4}, 5, 6]~ trở thành ~[\mathbf{1}, \mathbf{4}, 2, 3, 5, 6]~;
• Bước 2: Dồn số ở vị trí ~1~ và vị trí ~4~ sang bên phải, dãy số ~[\mathbf{1}, 4, 2, \mathbf{3}, 5, 6]~ trở thành ~[4, 2, 5, 6, \mathbf{1}, \mathbf{3}]~.

Yêu cầu: Với dãy số ban đầu, sau khi thực hiện liên tục ~K~ lượt, xác định vị trí của giá trị ~X~ và giá trị của phần tử ở vị trí ~Y~.

Dữ liệu vào từ tệp văn bản CHINHPHUONG.INP:

• Một dòng duy nhất gồm bốn số nguyên dương ~N, K, X, Y~ ~(1 \le X, Y \le N \le 10^{12};\ K \le 10^6)~.

Kết quả ghi ra tệp văn bản CHINHPHUONG.OUT:

• Một dòng duy nhất chứa hai số nguyên dương là kết quả bài toán.

Ràng buộc:

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N, K \le 1000~;
• ~20\%~ số test khác ứng với ~20\%~ số có ~K = 1~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

6 1 3 6

Sample Output 1

6 3

Giải thích: Dãy sau thực hiện ~1~ lượt: ~[4,2,5,6,1,3]~; Vị trí của giá trị ~3~ là ~6~. Giá trị của phần tử ở vị trí ~6~ là ~3~.

Sample Input 2

6 2 1 1

Sample Output 2

3 6

Giải thích: Dãy sau thực hiện ~2~ lượt: ~[6,2,1,3,4,5]~; Vị trí của giá trị ~1~ là ~3~. Giá trị của phần tử ở vị trí ~1~ là ~6~.

Độ khó: Khó (4/4 điểm)

Một khu đất được chia thành ~N~ mảnh liền kề đánh số từ ~1~ đến ~N~. Mảnh thứ ~i~ có độ cao là số nguyên không âm ~H_i~.

Có ~M~ nhà đầu tư tham gia dự án. Nhà đầu tư thứ ~i~ muốn thuê toàn bộ các mảnh đất thuộc đoạn ~[L_i, R_i]~ và chỉ chấp nhận khi ~H_j = 0~ ~(L_i \le j \le R_i)~. Các yêu cầu là độc lập, có thể nhiều nhà đầu tư muốn thuê cùng một đoạn.

Đội thi công nhận được ~Q~ chỉ thị liên tiếp. Mỗi chỉ thị chọn một vị trí ~x~ đang có ~H_x > 0~ và thực hiện giảm ~H_x~ đi ~1~.

Yêu cầu: Sau mỗi chỉ thị, hãy cho biết số lượng nhà đầu tư đang được thỏa mãn.

Trong một số trường hợp để bảo mật thông tin, vị trí ~x_i~ có thể được mã hóa. Dữ liệu cung cấp giá trị ~y_i~ và tham số ~\theta~:

• Nếu ~\theta = 0~, ~x_i = y_i~ (không mã hoá);
• Nếu ~\theta = 1~, ~x_i = (y_i + lastans) \% N + 1~, trong đó ~lastans~ là đáp án ngay trước chỉ thị thứ ~i~.

Trước chỉ thị đầu tiên, ~lastans~ là số lượng nhà đầu tư thỏa mãn ở trạng thái ban đầu.

Dữ liệu vào từ tệp văn bản SANLAP.INP:

• Dòng đầu tiên chứa bốn số nguyên ~N, M, Q, \theta~ ~(1 \le N, M, Q \le 5 \times 10^5;\ \theta \in \{0, 1\})~;
• Dòng thứ hai chứa ~N~ số nguyên ~H_1, H_2, \ldots, H_N~ ~(0 \le H_i \le 5 \times 10^5)~;
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i, R_i~ ~(1 \le L_i \le R_i \le N)~;
• Dòng cuối cùng chứa ~Q~ số nguyên ~y_1, y_2, \ldots, y_Q~ ~(0 \le y_i < 10^9)~.

Dữ liệu bảo đảm sau khi giải mã luôn có ~1 \le x_i \le N~ và ~H_{x_i} > 0~ ngay trước khi thực hiện chỉ thị.

Kết quả ghi ra tệp văn bản SANLAP.OUT:

• In ~Q~ dòng: dòng thứ ~i~ là số lượng nhà đầu tư thỏa mãn sau chỉ thị thứ ~i~.

Ràng buộc:

• Có ~20\%~ số test ứng với ~20\%~ số điểm có ~N, M, Q \le 400~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N, M, Q \le 4000~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm các đoạn yêu cầu đôi một rời nhau và được cho theo thứ tự từ trái sang phải;
• ~15\%~ số test khác ứng với ~15\%~ số điểm có ~N \le 4000~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm có ~N \le 2 \times 10^5~ và ~\theta = 0~;
• ~15\%~ số test còn lại ứng với ~15\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

6 4 6 0
1 1 1 2 1 1
2 6
3 4
5 5
4 4
4 3 4 2 5 6

Sample Output 1

0
0
2
2
3
4

Giải thích: Sau chỉ thị thứ ba, hai mảnh ~3~ và ~4~ đều có độ cao ~0~, nên hai nhà đầu tư có yêu cầu ~[3,4]~ và ~[4,4]~ được thỏa mãn. Sau chỉ thị cuối cùng, các mảnh từ ~2~ đến ~6~ đều bằng ~0~ và cả bốn nhà đầu tư đều được thỏa mãn.

Sample Input 2

5 5 6 1
4 1 1 1 0
3 3
3 4
2 2
4 4
3 4
5 0 6 1 1 0

Sample Output 2

0
0
1
2
5
5

Giải thích: Khi ~\theta = 1~, trước chỉ thị đầu tiên, không có nhà đầu tư nào thoả mãn nên ~lastans = 0~, vị trí thực tế ~x_1 = (5 + 0) \% 5 + 1 = 1~, ~H_1~ giảm từ ~4~ xuống ~3~. Trước chỉ thị thứ tư, ~lastans = 1~ nên vị trí thực tế là ~x_4 = (1 + 1) \% 5 + 1 = 3~, ~H_3~ giảm từ ~1~ xuống ~0~.

Độ khó: Khó (4/4 điểm)

Một hệ thống gồm ~N~ cảm biến được xếp thành hàng, đánh số từ ~1~ đến ~N~. Cảm biến thứ ~i~ có tần số hiệu chỉnh là số nguyên dương ~A_i~. Mức đồng bộ của một nhóm cảm biến được tính bằng ước chung lớn nhất của các tần số trong nhóm.

Yêu cầu: Xử lý ~Q~ thao tác thuộc một trong hai loại:

• Loại 1 — 1 L R X: tăng tần số của mọi cảm biến ~A_i~ ~(L \le i \le R)~ thêm ~X~;
• Loại 2 — 2 L R: xét các cảm biến ở các vị trí ~L, L + 1, \ldots, R~; được phép loại không quá một cảm biến. Hãy tìm mức đồng bộ lớn nhất có thể của các cảm biến còn lại.

Truy vấn có ~L = R~ luôn có đáp án ~A_L~ (không loại bỏ cảm biến nào).

Dữ liệu vào từ tệp văn bản CONGHUONG.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~N, Q~ ~(1 \le N, Q \le 2 \times 10^5)~;
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le 10^9)~;
• Mỗi dòng trong ~Q~ dòng tiếp theo có một trong hai dạng:
  • 1 L R X, với ~1 \le L \le R \le N~ và ~1 \le X \le 10^9~;
  • 2 L R, với ~1 \le L \le R \le N~.

Kết quả ghi ra tệp văn bản CONGHUONG.OUT:

• Với mỗi thao tác loại ~2~, in ra trên một dòng đáp án tương ứng.

Ràng buộc:

• Có ~20\%~ số test ứng với ~20\%~ số điểm có ~N, Q \le 300~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N, Q \le 2000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm không có thao tác loại ~1~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm mọi thao tác loại ~1~ đều có ~L = R~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

3 3
6 10 15
2 1 3
1 2 3 2
2 1 3

Sample Output

5
6

Giải thích:

• Thao tác ~1~: loại bỏ cảm biến đầu tiên có giá trị ~6~, kết quả là ước chung lớn nhất của ~10~ và ~15~ là ~5~.
• Thao tác ~2~: sau phép cộng, dãy là ~[6,12,17]~.
• Thao tác ~3~: loại bỏ cảm biến cuối cùng có giá trị ~17~, kết quả là ước chung lớn nhất của ~6~ và ~12~ là ~6~.

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Công ty vận tải AZ nhận chở hàng cho ~n~ xã miền núi được đánh số từ ~1~ đến ~n~. Các xã nối với nhau bằng ~m~ con đường hai chiều. Con đường thứ ~j~ nối giữa hai xã ~(x_j, y_j)~ và có độ dốc ~w_j~. Giữa hai xã có thể có nhiều con đường khác nhau và độ dốc của chúng không nhất thiết khác nhau. Không có con đường nào vòng trực tiếp về đúng xã nó xuất phát.

Xe chở hàng là loại xe container có đầu kéo chuyên dụng. Chi phí một chuyến đi được tính bằng độ dốc cao nhất mà xe phải vượt qua trong hành trình.

Tài xế có thể đi vòng hoặc đi qua lại một xã nhiều lần để đi đến đích.

Yêu cầu: Với mỗi kho hàng tại xã ~u~, hãy tính tổng chi phí thấp nhất đến ~n-1~ xã còn lại.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(1 \le n \le 2 \cdot 10^5; n-1 \le m \le 5 \cdot 10^5)~.
• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~x_j, y_j, w_j~ ~(1 \le x_j, y_j \le n; x_j \ne y_j; 1 \le w_j \le 10^9)~.

Output

Một dòng chứa ~n~ số nguyên, số thứ ~u~ là tổng chi phí thấp nhất ứng với kho hàng đặt tại xã ~u~. Khi ~n=1~ thì không có chuyến nào, in ra số ~0~.

Scoring

Sample Input 1

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

Sample Output 1

15 12 12 13

Sample Input 2

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

Sample Output 2

21 21 24 20 20

Sample Input 3

3 4
1 2 9
1 2 2
2 3 5
1 3 8

Sample Output 3

7 7 10

Notes

Ví dụ 1 khi đặt kho hàng tại xã ~2~:

• Chuyến đi từ kho hàng qua xã ~1~ có hành trình ~2 \rightarrow 1~ với chi phí nhỏ nhất là ~5~.
• Chuyến đi từ kho hàng qua xã ~3~ có hành trình ~2 \rightarrow 3~ với chi phí nhỏ nhất là ~3~.
• Chuyến đi từ kho hàng qua xã ~4~ có hành trình ~2 \rightarrow 3 \rightarrow 4~ với chi phí nhỏ nhất là ~4~.

Vậy tổng chi phí vận chuyển đến các xã còn lại là: ~5+3+4=12~.