|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
1 sec |
32 MB |
| Case 5 |
1 sec |
32 MB |
| Case 6 |
1 sec |
32 MB |
Description
Frank Lee's class is on a field trip, and there are N students standing in a line, numbered from 1 to N from left to right. Each student's height is represented by an integer, forming a sequence H of length N.
The teacher wants to know the difference between the maximum and minimum heights within any continuous subinterval of length K during the trip.
Your task is to help the teacher calculate and list these differences for all continuous subintervals of length K.
Input
- The first line contains two integers N and K, representing the total number of students and the length of the continuous subinterval.
- The second line contains N integers, representing the heights H of each student from left to right.
Constraints
- 1 ≤ Hi ≤ 109
- 1 ≤ K ≤ N ≤ 2 × 105
Output
- Output N−K+1 lines. The i-th line should contain a single integer, representing the difference between the maximum and minimum heights in the continuous subinterval [i, i+K-1].
Testcases
- Testcases 1, 2: guarantee that K ≤ 10 .
- Testcases 3, 4: guarantee the height of students is non-decreasing (from left to right).
- Testcases 5, 6: no additional constraint.
Hint
Think about how to quickly derive the answer for one interval from the answer of another interval using only a few insert and delete operations in std::set or std::multiset.
Tags