Submission #53107562

---

Source Code Expand

#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class segtree{
public:
	static const int N=1<<18;
	int dp[1<<19];
	segtree(){
		memset(dp,0,sizeof(dp));
	}
	void update(int k,int v){
		k+=N-1;
		dp[k]=v;
		while(k>0){
			k=(k-1)/2;
			dp[k]=max(dp[k*2+1],dp[k*2+2]);
		}
	}

	int query(int a,int b,int k=0,int l=0,int r=N){
		if(b<=l || r<=a)return -99999999;
		if(a<=l && r<=b)return dp[k];
		int mid=(l+r)/2;
		int vl=query(a,b,k*2+1,l,mid);
		int vr=query(a,b,k*2+2,mid,r);
		return max(vl,vr);
	}
};

int n,k;
int p[200005];
segtree seg,segm;

int main(void){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&p[i]);
        p[i]--;
        seg.update(p[i],i);
        segm.update(p[i],-i);
    }
    int ans=9999999;
    for(int i=0;i<=n-k;i++){
        int v1=seg.query(i,i+k);
        int v2=-segm.query(i,i+k);
        ans=min(ans,v1-v2);
        //printf("%d %d\n",v1,v2);
    }
    printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result