省联合模拟1 SSY的形态 HSDFZ4573

Description

给定N个数，第 i 个数的形态描述为一个正整数 Ai，定义形态i 和形态j 的差异为|Ai - Aj|。

SSY在给定一个指令后会发生形态变化，它会从当前形态变化为其他形态中与其差异第 K 小的形态。如果差异第 K小的形态不是唯一的，那么它会变化为 Ai 比较小的那个形态。

SSY 的好奇心驱使，他想知道从每个形态开始接受一个指令后会是什么形态。

Input

第一行包含两个整数 N, K。

之后一行包含 N个整数 A1, A2, A3, ..., AN-1, AN。

Output

一行内输出 N个整数 S1, S2, S3, ..., SN-1, SN，其中 Si 表示从形态 i变化一次之后的形态描述值。行末有一空格

Sample Input

5 2 
1 2 4 7 10

Sample Output

4 4 1 4 4

HINT

对于 100% 的数据，1≤K＜N≤10^6，1≤A1＜A2＜...＜AN≤10^18 。

Solve

维护一个区间[L,R)，让L或者R-1始终是答案。

居然没想到。。。%jms大佬

Code

#include <bits/stdc++.h>
  
using namespace std;
  
long long nextLong()
{
    long long ret=0;
    char a;
    a=getchar();
    while(!isdigit(a))
    {
        a=getchar();
    }
    while(isdigit(a))
    {
        ret=ret*10+a-'0';
        a=getchar();
    }
    return ret;
}
  
long long A[10+int(1e6)];
  
int main()
{
    long long N,K;
    N=nextLong();
    K=nextLong();
    for(long long i=0;i<N;++i)
    {
        A[i]=nextLong();
    }
    int L=0,R=K+1;
    for(long long i=0;i<N;++i)
    {
        while(i>R-1)
        {
            L++;
            R++;
        }
        while(R<N&&A[R]-A[i]<A[i]-A[L])
        {
            L++;
            R++;
        }
        if(A[R-1]-A[i]>A[i]-A[L])
        {
            cout<<A[R-1]<<' ';
        }
        else
        {
            cout<<A[L]<<' ';
        }
    }
}