2030 : พิสัยพิเศษ (range)
Problem type : Batch
Time limit : 0.4 second(s)
Memory limit : 64 megabyte(s)
    เรามีลำดับของจำนวนเต็ม N จำนวน แทนด้วย a1,a2,a3,…,aN เราต้องการทราบจำนวนของลำดับย่อย ai,ai+1,ai+2,…,aj (ซึ่ง i≤j) ที่มีพิสัยของลำดับย่อยเป็นจำนวนเต็มที่อยู่ในช่วง [p,q] ว่ามีกี่ลำดับย่อย
    นิยาม พิสัยของลำดับจำนวนหนึ่ง ๆ คือผลต่างของค่าสูงสุดและต่ำสุดของลำดับดังกล่าว  ดังนั้นพิสัยของลำดับย่อย ai,ai+1,ai+2,…,aj ก็คือ max(ai,ai+1,ai+2,…,aj) - min(ai,ai+1,ai+2,…,aj)
    สมมติลำดับของจำนวนเต็ม 7 ตัวมี 1, 7, 4, 3, 9, 6, 8 พบว่าจะมีลำดับย่อยทั้งหมด 13 ลำดับย่อยที่มีค่าพิสัยอยู่ในช่วงตั้งแต่ 4 ถึง 6 ได้แก่ 1-7-4-3,  1-7-4,  1-7,  7-4-3-9-6-8,  7-4-3-9-6,  7-4-3-9,  7-4-3,  4-3-9-6-8,  4-3-9-6,  4-3-9,  3-9-6-8, 3-9-6 และ 3-9 

งานของคุณ

    คุณจะต้องรับลำดับของจำนวนเต็ม แล้วหาว่ามีลำดับย่อยกี่ลำดับที่มีค่าพิสัยมากกว่าหรือเท่ากับ p และน้อยกว่าหรือเท่ากับ q

ข้อมูลนำเข้า

    บรรทัดแรกมีจำนวนเต็มสามจำนวนคือ N,p,q บอกความยาวของลำดับจำนวนและช่วงพิสัยที่สนใจตามลำดับ (1≤N≤1,000,000 และ 0≤p≤q≤10,000,000)
    อีก N บรรทัดถัดมา จะมีข้อมูลของจำนวนในลำดับ โดยข้อมูลในบรรทัดที่ i+1 จะมีจำนวนเต็ม a_i ซึ่งหมายถึงจำนวนที่ i ของลำดับ (0≤a_i≤10,000,000)

ข้อมูลส่งออก

    มีจำนวนเต็มจำนวนเดียวบอกจำนวนของลำดับย่อยที่มีพิสัยอยู่ในช่วง [p,q]

การให้คะแนน

    ชุดข้อมูลทดสอบมูลค่าไม่เกิน 40 คะแนน มีค่า N≤1,000    ชุดข้อมูลทดสอบมูลค่าไม่เกิน 70 คะแนน มีค่า N≤100,000 และ ในทุกชุดข้อมูลทดสอบมีค่า N≤1,000,000

 


โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มาTOI.C:05-2009

 


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
7 4 6
1
7
4
3
9
6
8
13

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

กำลังออนไลน์: 17 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)