trang chủ / đề bài / icpcwf20_e

Máy sinh địa hình

Đề bài

Mô tả

Interactive Creative Players Collective (ICPC) đang phát triển một trò chơi máy tính mới và muốn sinh ra các địa hình trông thật tự nhiên. Một kỹ sư của ICPC đề xuất một thuật toán lấy cảm hứng từ các quá trình địa chất. Thuật toán bắt đầu từ một địa hình phẳng rồi liên tục biến đổi nó bằng cách nâng lên hoặc hạ xuống các khối liền nhau, tạo thành các địa lũy (khối được nâng lên) và địa hào (khối bị hạ xuống). Các khối được nâng hoặc hạ được chọn ngẫu nhiên. ICPC hy vọng cách này sẽ cho ra những địa hình giống thật.

Nhiệm vụ của bạn là thực hiện một dãy biến đổi bất kỳ như vậy và in ra địa hình thu được. Địa hình được biểu diễn bởi một dãy n độ cao nguyên, mỗi độ cao ứng với một điểm nguyên từ 1 tới n trên trục hoành. Hình 1 minh họa một ví dụ bằng cách nối các độ cao bằng các đoạn thẳng.

Hình 1: Địa hình sinh ra bởi ví dụ 1.

Ban đầu độ cao bằng 0 tại cả n điểm. Địa hình phẳng này lần lượt chịu một dãy biến đổi. Mỗi biến đổi là một trong bốn thao tác sau, với hai tham số nguyên x1≤x2:

  • R (Raise, nâng): tăng độ cao thêm 1 tại mọi điểm từ x1 tới x2 (tính cả hai đầu).
  • D (Depress, hạ): giảm độ cao đi 1 tại mọi điểm từ x1 tới x2 (tính cả hai đầu).
  • H (Hill, đồi): thêm một ngọn đồi hình tuyến tính trong đoạn từ x1 tới x2.
  • V (Valley, thung lũng): thêm một thung lũng hình tuyến tính trong đoạn từ x1 tới x2.

Thêm một ngọn đồi vào địa hình hiện tại được thực hiện như sau. Độ cao tại các điểm x1 và x2 được tăng thêm 1. Nếu x2−x1>1, độ cao tại các điểm x1+1 và x2−1 được tăng thêm 2. Nếu x2−x1>3, độ cao tại các điểm x1+2 và x2−2 được tăng thêm 3, và cứ thế tiếp tục. Hình 2 là một ví dụ. Thêm một thung lũng được thực hiện theo cùng cách, chỉ khác là độ cao bị giảm đi thay vì được tăng lên. Mức thay đổi độ cao lớn nhất xảy ra ở chính giữa x1 và x2. Nếu x2−x1 lẻ thì có hai điểm kề nhau cùng có mức thay đổi lớn nhất, ngược lại chỉ có một điểm.

Hình 2: Địa hình sinh ra bởi ví dụ 2.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k: n là số điểm và k là số biến đổi. Các điểm trên trục hoành được đánh số từ 1 tới n.

Mỗi dòng trong k dòng tiếp theo mô tả một biến đổi, gồm một ký tự c và hai số nguyên x1, x2: c (một trong các ký tự R, D, H, V) cho biết thao tác, còn x1 và x2 là các tham số của thao tác.

Dữ liệu ra

In ra n dòng, dòng thứ i chứa độ cao tại điểm i sau khi thực hiện tất cả các biến đổi theo thứ tự đã cho.

Ràng buộc

  • 1≤n≤200000, 0≤k≤200000.
  • c∈{R, D, H, V}, 1≤x1≤x2≤n.

Ví dụ

Input Output Giải thích
20 13
H 12 13
D 5 18
R 13 14
R 8 16
H 2 3
V 10 19
V 3 13
R 8 13
V 3 10
D 5 18
V 11 12
R 1 6
R 14 19
1
2
0
-3
-7
-9
-11
-9
-7
-6
-6
-5
-3
-4
-5
-4
-4
-3
0
0
Địa hình thu được là Hình 1.
7 1
H 1 6
1
2
3
3
2
1
0
Ngọn đồi trên đoạn [1,6]: x2−x1=5 lẻ nên hai điểm 3 và 4 cùng cao nhất (3). Điểm 7 nằm ngoài đoạn nên vẫn cao 0 (Hình 2).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0