D. Strip

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Alexandra has a paper strip with n numbers on it. Let's call them ai from left to right.

Now Alexandra wants to split it into some pieces (possibly 1). For each piece of strip, it must satisfy:

• Each piece should contain at least l numbers.
• The difference between the maximal and the minimal number on the piece should be at most s.

Please help Alexandra to find the minimal number of pieces meeting the condition above.

Input

The first line contains three space-separated integers n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).

The second line contains n integers ai separated by spaces ( - 109 ≤ ai ≤ 109).

Output

Output the minimal number of strip pieces.

If there are no ways to split the strip, output -1.

Sample test(s)

input

7 2 2 1 3 1 2 4 1 2

output

3

input

7 2 2 1 100 1 100 1 100 1

output

-1

Note

For the first sample, we can split the strip into 3 pieces: [1, 3, 1], [2, 4], [1, 2].

For the second sample, we can't let 1 and 100 be on the same piece, so no solution exists.

 

 

 

 

 题意是给出一个长度为n的序列，问最少能够分割多少分。

 使得，每一分的长度大于等于l，最大值与最少值的差值最大为s 。

 我的方法是3颗线段树，2颗维护最大最小值， 1棵维护 dp[i-1]+1 最小的位置。 

 然后二分出尽量左的位置使得最大最小值差值最大不超过s ，

 然后从这个位置到当前位置取出 dp[i-1]+1 最小的位置。然后再更新。

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
            
           
          
         
        
       
      

 

之前一直不会set...

在cf上看别人的代码，被完爆码量。

 

 

begin() 返回指向第一个元素的迭代器

clear() 清除所有元素

count() 返回某个值元素的个数

empty() 如果集合为空，返回true(真）

end() 返回指向最后一个元素之后的迭代器，不是最后一个元素

equal_range() 返回集合中与给定值相等的上下限的两个迭代器

erase() 删除集合中的元素

find() 返回一个指向被查找到元素的迭代器

get_allocator() 返回集合的分配器

insert() 在集合中插入元素

lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器

key_comp() 返回一个用于元素间值比较的函数

max_size() 返回集合能容纳的元素的最大限值

rbegin() 返回指向集合中最后一个元素的反向迭代器

rend() 返回指向集合中第一个元素的反向迭代器

size() 集合中元素的数目

swap() 交换两个集合变量

upper_bound() 返回大于某个值元素的迭代器

value_comp() 返回一个用于比较元素间的值的函数

 

 

用两个set。

一个维护区间范围。

一个维护dp[i-1]+1最小。

set的好处是可以按照给出值查找并删除那个元素。

就相当于有两棵现成的红黑树，替代了线段树的功能了。

 

 

#include 
      
       #define X first#define Y second#define INF 1000000009using namespace std;typedef pair
       
         pii;int n, s, l, a[100005];int dp[100005];set 
        
          S, R;int main(){  scanf("%d %d %d", &n, &s, &l);  for(int i = 1; i <= n; i ++)    scanf("%d", &a[i]);  memset(dp, 0, sizeof dp);    int j = 1;  for(int i = 1; i <= n; i ++){    S.insert(pii(a[i], i));    while(!S.empty() && S.rbegin()->X - S.begin()->X > s){      S.erase(pii(a[j], j));      j ++;    }    if(i >= l && dp[i - l] != -1)      R.insert(pii(dp[i - l], i - l));    while(!R.empty() && R.begin()->Y < j - 1)      R.erase(R.begin());    if(R.empty())      dp[i] = -1;    else      dp[i] = R.begin()->X + 1;  }  printf("%d\n", dp[n]);  return 0;}