2019ACM-ICPC南京网络赛Greedy Sequence

Greedy Sequence

限制

5000 ms

256 MB

 

You're given a permutation a of length n (1 ≤ n ≤ 105).

For each i ∈ [1, n], construct a sequence si by the following rules:

1. si[1] = i;

2. The length of si is n, and for each j ∈ [2, n], si[j] ≤ si[j − 1];

3. First, we must choose all the possible elements of si from permutation a. If the index

of si[j] in permutation a is pos[j], for each j ≥ 2, ∣pos[j] − pos[j − 1]∣ ≤ k (

1 ≤ k ≤ 105). And for each si, every element of si must occur in a at most once.

4. After we choose all possible elements for si, if the length of si is smaller than n, the

value of every undetermined element of si is 0;

5. For each si, we must make its weight high enough.

Consider two sequences C = [c1, c2, ...cn] and D = [d1, d2, ..., dn], we say the weight

of C is higher than that of D if and only if there exists an integer k such that 1 ≤ k ≤ n,

ci = di for all 1 ≤ i < k, and ck > dk .

If for each i ∈ [1, n], ci = di, the weight of C is equal to the weight of D.

For each i ∈ [1, n], print the number of non-zero elements of si separated by a space.It's guaranteed that there is only one possible answer.

 

Input

 

There are multiple test cases.

The fifirst line contains one integer T(1 ≤ T ≤ 20), denoting the number of test cases.

Each test case contains two lines, the fifirst line contains two integers n and k (

1 ≤ n, k ≤ 105), the second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ n)

separated by a space, which is the permutation a.

 

Output

 

For each test case, print one line consists of n integers ∣s1∣, ∣s2∣, ..., ∣sn∣ separated by a

space.

∣si∣ is the number of non-zero elements of sequence si.

There is no space at the end of the line.

 

 

Sample Input 1

2

3 1

3 2 1

7 2

3 1 4 6 2 5 7

 

Sample Output 1

1 2 3

1 1 2 3 2 3 3

前面的ans对后面的ans有贡献，用 num [ i ] 存  len ( S i )，然后找到满足条件的 a[  j  ]  （即  abs（j - i）<=k ），len ( S i ) =  1 + num [ a[ j ] ]。

 题目给的5000ms，1014ms就过了，嗨森。。（不过应该还可以更快，比赛的时候sb了，加了个memset。。。）

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
struct NODE
{
    int data;
    int id;
}node[maxn];
bool cmp(NODE a,NODE b)
{
    return a.data<b.data;
}
int num[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&node[i].data);
            node[i].id=i;
        }
        sort(node+1,node+n+1,cmp);
        //memset(num,0,sizeof(num));
        for(int i=1;i<=n;++i)
        {
            int len=1;
            int pos=node[i].id;
            for(int j=i-1;j>=1;--j)
            {
                if(abs(pos-node[j].id)<=k)
                {
                    len+=num[j];
                    break;
                }
            }
            num[i]=len;
            printf("%d",len);
            if(i<n)printf(" ");
            else printf("
");
        }
    }
    return 0;
}