1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
#include <cstdlib> #include <cstring> int n,k,a[1000005],d1[1000005][2],d2[1000005][2], f1=0,f2=0,r1=1,r2=1,ans[1000005][2]; void (int at,int p){ while(r1>f1&&d1[f1][1]<=at-k) f1++; while(r2>f2&&d2[f2][1]<=at-k) f2++; while(r1>f1&&d1[r1-1][0]>p) d1[r1-1][0]=d1[r1-1][1]=0,r1--; while(r2>f2&&d2[r2-1][0]<p) d2[r2-1][0]=d2[r2-1][1]=0,r2--; d1[r1][0]=p,d1[r1++][1]=at; d2[r2][0]=p,d2[r2++][1]=at; } int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&a[i]); i=(k==1)?0:1; d1[0][0]=d2[0][0]=a[0]; d1[0][1]=d2[0][1]=0; for(;i<n;i++){ in(i,a[i]); ans[i][0]=d1[f1][0]; ans[i][1]=d2[f2][0]; } for(i=k-1;i<n-1;i++) printf("%d ",ans[i][0]); printf("%dn",ans[n-1][0]); for(i=k-1;i<n-1;i++) printf("%d ",ans[i][1]); printf("%dn",ans[n-1][1]); return 0; }
|
近期评论