[ ลืมรหัสผ่าน | ลงทะเบียนสมาชิกใหม่ ]    
  


1008 : Skyline
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
สถิติโจทย์ข้อนี้ : ใช้เวลาน้อยที่สุด ทั้งหมด

รัฐบาลวางแผนสร้างเมืองใหม่บนพื้นที่ราบที่มีระดับเสมอกัน โดยกำหนดให้อาคารที่จะสร้างแต่ละหลังมีรูปทรงเป็นสี่เหลี่ยมผืนผ้า หลังจากที่มีการสร้างอาคารแล้วเมื่อมองตัวเมืองจากระยะไกล จะเห็นเส้นขอบฟ้าตามแนวเส้นขอบของอาคาร และทุกครั้งที่มีการสร้างอาคารเพิ่มขึ้น เส้นขอบฟ้าของตัวเมืองจะเปลี่ยนแปลงไป

อาคารที่จะสร้างขึ้นแต่ละหลัง กำหนดด้วยจำนวนเต็มบวกสามจำนวนคือ ( Li , Hi , Ri ) เมื่อ Li และ Ri เป็นตำแหน่งตามแกนนอนด้านซ้ายและขวาของอาคารลำดับที่ i ตามลำดับ ส่วน Hi เป็นความสูงของอาคารนั้น เช่น (1, 11, 5) หมายถึง อาคารที่สร้างขึ้นโดยมีขอบด้านซ้ายอยู่ที่ตำแหน่งที่ 1 ขอบด้านขวาอยู่ที่ตำแหน่งที่ 5 ของแกนนอน และมีความสูงเป็น 11 หน่วย เมื่อสร้างอาคารนี้เสร็จจะได้เส้นขอบฟ้าใหม่เป็น (1, 11, 5, 0) นั่นคือ ที่ตำแหน่งที่ 1 ขอบฟ้ายกขึ้นสูง 11 หน่วยตามความสูงของอาคารไปจนถึงตำแหน่งที่ 5 แล้วความสูงลดลงเป็น 0



แผนภาพด้านซ้ายมือแสดงตัวเมืองที่มีการสร้างอาคารแล้ว 8 หลัง ซึ่งอาคารแต่ละหลังมีข้อมูลดังนี้คือ (1, 11, 5), (2, 6, 7), (12, 7, 16), (14, 3, 25), (19, 18, 22), (3, 13, 9), (23, 13, 29), และ (24, 4, 28) ทำให้เกิดเส้นขอบฟ้าใหม่ตามแผนภาพด้านขวามือ ซึ่งแทนด้วยลำดับตัวเลขดังนี้คือ (1, 11, 3, 13, 9, 0, 12, 7,16, 3, 19, 18, 22, 3, 23, 13, 29, 0) โดยค่าที่พิมพ์ด้วยตัวหนาคือความสูงของเส้นขอบฟ้า

จงเขียนโปรแกรมคำนวณหาเส้นขอบฟ้าจากข้อมูลของอาคารที่กำหนดให้ และแสดงผล

ข้อมูลนำเข้า
1. บรรทัดแรกเป็นจำนวนอาคารที่ต้องการหาเส้นขอบฟ้า มีค่าตั้งแต่ 1 ถึง 3,000
2. บรรทัดต่อไปแต่ละบรรทัดเป็นข้อมูลของอาคารแต่ละหลังในรูปแบบ Li Hi Ri โดยแต่ละตัวมีค่าตั้งแต่ 1 ถึง 255
3. ระหว่างข้อมูลแต่ละตัวในข้อ ๒. คั่นด้วยเว้นวรรค 1 วรรค

ข้อมูลส่งออก
1. ผลลัพธ์ของโปรแกรมมีเพียงบรรทัดเดียว ได้แก่ เส้นขอบฟ้าที่เกิดจากข้อมูลของอาคารที่เป็นข้อมูลนำเข้า โดยเส้นขอบฟ้ามีรูปแบบดังนี้ v1 v2 v3 … vn-2 vn-1 vn เมื่อ i เป็นจำนวนคี่ vi จะแทนตำแหน่งของเส้นขอบฟ้าตามแกนนอน และ เมื่อ i เป็นจำนวนคู่ v i แทนความสูงของเส้นขอบฟ้าที่ตำแหน่งนั้น ด้วยเหตุนี้ vn จึงมีค่าเป็น 0 เนื่องจากเส้นขอบฟ้าลดลงสู่ระดับพื้น
2. ผลลัพธ์แต่ละจำนวนให้คั่นด้วยเว้นวรรค 1 วรรค

ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 2 มหาวิทยาลัยบูรพา

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
2
1  11  5
2  6  7 		1 11 5 6 7 0
8
1  11  5
2  6  7
12  7  16
14  3  25
19  18  22
3  13  9
23  13  29
24  4  28 		1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้