Codeforces Round #271 (Div. 2) E. Pillars 线段树优化dp-白红宇

Codeforces Round #271 (Div. 2) E. Pillars 线段树优化dp

阅读量：4487 次

发布时间：2019-06-08

本文共 3301 字，大约阅读时间需要 11 分钟。

Marmot found a row with n pillars. The i-th pillar has the height of hi meters. Starting from one pillar i1, Marmot wants to jump on the pillars i2, ..., ik. (1 ≤ i1 < i2 < ... < ik ≤ n). From a pillar i Marmot can jump on a pillar j only if i < j and |hi - hj| ≥ d, where |x| is the absolute value of the number x.

Now Marmot is asking you find out a jump sequence with maximal length and print it.

Input

The first line contains two integers n and d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109).

The second line contains n numbers h1, h2, ..., hn (1 ≤ hi ≤ 1015).

Output

The first line should contain one integer k, the maximal length of a jump sequence.

The second line should contain k integers i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), representing the pillars' indices from the maximal length jump sequence.

If there is more than one maximal length jump sequence, print any.

Examples

input

5 2 1 3 6 7 4

output

4 1 2 3 5

input

10 3 2 1 3 6 9 11 7 3 20 18

output

6 1 4 6 7 8 9

Note

In the first example Marmot chooses the pillars 1, 2, 3, 5 with the heights 1, 3, 6, 4. Another jump sequence of length 4 is 1, 2, 4, 5.

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                using namespace std;#define LL long long#define pi (4*atan(1.0))#define eps 1e-8#define bug(x) cout<<"bug"<
                 
                  <
                  
                   >1; if(p<=mid)update(p,c,l,mid,pos<<1); else update(p,c,mid+1,r,pos<<1|1); maxx[pos]=max(maxx[pos<<1],maxx[pos<<1|1]); } int query(int L,int R,int l,int r,int pos) { if(L<=l&&r<=R)return maxx[pos]; int mid=(l+r)>>1; int ans=0; if(L<=mid)ans=max(ans,query(L,R,l,mid,pos<<1)); if(R>mid)ans=max(ans,query(L,R,mid+1,r,pos<<1|1)); return ans; }}tree;LL a[N],b[N];int n;LL k;int big(LL x){ int pos=lower_bound(b,b+2+n,x)-b; return pos;}int low(LL x){ int pos=upper_bound(b,b+2+n,x)-b-1; return pos;}int dp[N];vector
                   
                    ans;int main(){ scanf("%d%lld",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); b[i]=a[i]; } sort(b+1,b+1+n); b[n+1]=INF; b[0]=-INF; for(int i=1;i<=n;i++) { LL pre=a[i]-k; LL nex=a[i]+k; int pos1=low(pre); int pos2=big(nex); //cout<
                    <<" "<
                     
                      <<" "<
                      
                       <<" "<
                       
                        <
                        
                         =1)maxx=max(maxx,tree.query(1,pos1,1,n,1));        if(pos2<=n)maxx=max(maxx,tree.query(pos2,n,1,n,1));        dp[i]=maxx+1;        tree.update(low(a[i]),maxx+1,1,n,1);    }    int maxx=0,pre=-1;    for(int i=1;i<=n;i++)    {        if(dp[i]>maxx)        {            maxx=dp[i];            pre=i;        }    }    ans.push_back(pre);    for(int i=pre-1;i>=1;i--)    {        if(abs(a[i]-a[pre])>=k&&dp[pre]==dp[i]+1)        {            pre=i;            ans.push_back(pre);        }    }    printf("%d\n",maxx);    for(int i=maxx-1;i>=0;i--)        printf("%d ",ans[i]);    return 0;}

转载于:https://www.cnblogs.com/jhz033/p/7258699.html

你可能感兴趣的文章