XKC , the captain of the basketball team , is directing a train of nn team members. He makes all members stand in a row , and numbers them 1 \cdots n1⋯n from left to right.
The ability of the ii-th person is w_iwi , and if there is a guy whose ability is not less than w_i+mwi+m stands on his right , he will become angry. It means that the jj-th person will make the ii-th person angry if j>ij>i and w_j \ge w_i+mwj≥wi+m.
We define the anger of the ii-th person as the number of people between him and the person , who makes him angry and the distance from him is the longest in those people. If there is no one who makes him angry , his anger is -1−1 .
Please calculate the anger of every team member .
Input
The first line contains two integers nn and m(2\leq n\leq 5*10^5, 0\leq m \leq 10^9)m(2≤n≤5∗105,0≤m≤109) .
The following line contain nn integers w_1..w_n(0\leq w_i \leq 10^9)w1..wn(0≤wi≤109) .
Output
A row of nn integers separated by spaces , representing the anger of every member .
样例输入复制
6 1
3 4 5 6 2 10
样例输出复制
4 3 2 1 0 -1
队友做的，没大有思路。
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define MAXN 500100
struct node
{
LL x;
LL y;
} a[MAXN*2];
LL b[MAXN],c[MAXN];
bool cmp(node u,node v)
{
return u.x<v.x;
}
int main()
{
LL n,m,i,j;
scanf("%lld%lld",&n,&m);
for(i=1; i<=n; i++)
{
scanf("%lld",&a[i].x);
a[i].y=i;
b[i]=a[i].x;
}
j=n;
sort(a+1,a+n+1,cmp);
bool flag=false;
for(i=1; i<=n; i++)
{
while(b[j]<a[i].x+m)
{
if(j==0)
{
flag=true;
break;
}
j--;
}
if(flag)
c[a[i].y]=-1;
else{
if(j<=a[i].y) c[a[i].y]=-1;
else
c[a[i].y]=j-a[i].y-1;
}
}
for(i=1; i<n; i++)
printf("%lld ",c[i]);
printf("%lld",c[n]);
return 0;
}
