Codeforces Round #278 (Div. 1) Strip （线段树二分 RMQ DP）

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.

Examples

input

7 2 2
1 3 1 2 4 1 2

output

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.

【题意】给你一个序列，让你分成若干份，对于每一份，要求最大值-最小值<=s，且每一份长度不小于L。求分得的最小份数，若不可分，输出-1.

【分析】考虑DP，dp[i]代表1~i分得的最小份数，则dp[i]=min(dp[j])+1,j当然得满足条件，首先i-j+1>=L,然后max[j,i]-min[j,i]<=s,考虑到区间最大值-最小值具有单调性，所以二分极限的j,然后判断一下j的可行性，可由j-1~i-L之间的最小dp值转移过来。区间最大最小值用RMQ，线段树维护区间dp最小值。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5+50;;
const int M = 160009;
const int mod = 1e9+7;
const double pi= acos(-1.0);
typedef pair<int,int>pii;
int n,len,s;
int dp[N];
int a[N],mi[N*4];
int mn[N][20],mx[N][20],mm[N];
void init() {
    for(int j=1; j<=mm[n]; ++j) {
        for(int i=1; i+(1<<j)-1<=n; ++i) {
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
}
int getmx(int l,int r) {
    int k = mm[r-l+1];
    return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int getmn(int l,int r) {
    int k = mm[r-l+1];
    return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
void upd(int l,int r,int rt,int pos){
    if(l==r){
        mi[rt]=dp[l];
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)upd(l,mid,rt<<1,pos);
    else upd(mid+1,r,rt<<1|1,pos);
    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
int qry(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return mi[rt];
    }
    int ret=inf,mid=(l+r)>>1;
    if(L<=mid)ret=min(ret,qry(L,R,l,mid,rt<<1));
    if(R>mid)ret=min(ret,qry(L,R,mid+1,r,rt<<1|1));
    return ret;
}
void solve(int pos){
    int l=1,r=pos,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        int minn=getmn(mid,pos);
        int maxn=getmx(mid,pos);
        if(maxn-minn<=s)r=mid-1,ans=mid;
        else l=mid+1;
    }
    if(ans==-1||pos-ans+1<len)dp[pos]=inf;
    else if(ans==1)dp[pos]=1;
    else dp[pos]=qry(max(ans-1,1),pos-len,1,n,1)+1;
}
int main(){
    mm[0]=-1;
    for(int i=1; i<N; ++i)mm[i]=(i&(i-1))?mm[i-1]:mm[i-1]+1;
    scanf("%d%d%d",&n,&s,&len);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),mn[i][0]=mx[i][0]=a[i];
    init();
    met(dp,inf);
    for(int i=1;i<=n;i++){
        if(i<len)dp[i]=inf;
        else solve(i);
        upd(1,n,1,i);
    }
    if(dp[n]>=inf)puts("-1");
    else printf("%d
",dp[n]);
    return 0;
}

Codeforces Round #278 (Div. 1) Strip （线段树 二分 RMQ DP）

Codeforces Round #278 (Div. 1) Strip （线段树二分 RMQ DP）