题目链接:https://nanti.jisuanke.com/t/41387

按wi的值建立权值线段树维护值为wi出现的最后位置,对于第i个人的答案,查询线段树[wi+m,max]区间的最大位置pos,令如果pos-i-1小于等于-1则是在i之后不存在大于等于wi+m的人,否则第i个人的答案即为pos-i-1。由于wi范围过大所以需对wi离散化

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define maxn 1000010
int n,m,mx[maxn<<];
ll w[maxn],x[maxn],li[maxn],ans[maxn];
void pushup(int rt)
{
mx[rt]=max(mx[rt<<],mx[rt<<|]);
}
void update(int L,int c,int l,int r,int rt)
{
if(l==r)
{
mx[rt]=c;
return ;
}
int mid=l+r>>;
if(L<=mid)update(L,c,ls);
else update(L,c,rs);
pushup(rt);
}
int query(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return mx[rt];
}
int mid=l+r>>,ret=;
if(L<=mid)ret=max(ret,query(L,R,c,ls));
if(R>mid)ret=max(ret,query(L,R,c,rs));
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int tot=;
for(int i=;i<=n;i++)
{
scanf("%lld",&w[i]);
x[++tot]=w[i];
x[++tot]=w[i]+m;
}
sort(x+,x++tot);
int nx=unique(x+,x++tot)-x-;
int L;
for(int i=;i<=n;i++)
{
L=lower_bound(x+,x++nx,w[i])-x;
update(L,i,,nx,);
}
for(int i=;i<=n;i++)
{
L=lower_bound(x+,x++nx,w[i]+m)-x;
L=query(L,nx,i,,nx,);
if(L==-)ans[i]=-;
else ans[i]=L-i-;
if(ans[i]<-)ans[i]=-;
}
for(int i=;i<n;i++)
printf("%lld ",ans[i]);
printf("%lld\n",ans[n]);
return ;
}

最新文章

  1. 阅读微信支付demo收获
  2. Centos7下配置Redis开机自启动
  3. 内置函数----整理、例题 、xmin
  4. C++主要数据类型在计算机中所占字节大小
  5. IDO分享 | 如何在centos下安装OpenCMS
  6. C#中abstract和virtual区别
  7. 配置文件——WebApp.config文件读取和修改
  8. echart 图表 在.net中生成图片的方法
  9. UITableView 详解 ()
  10. (转)手把手教你如何架设VPN
  11. 关于Tesseract3.01的使用方法
  12. M0、M1、M2、M3都是用来反映货币供应量的重要指标
  13. MVC快速分页
  14. python--sorted函数
  15. 一步一步创建ASP.NET MVC5程序[Repository+Autofac+Automapper+SqlSugar](四)
  16. [开源]使用C# 对CPU卡基本操作封装
  17. jmeter 使用问题
  18. Linux网络 - 数据包的接收过程(转)
  19. Golang自定义包导入
  20. ssr 之Nuxt.js

热门文章

  1. 2018-9-1-win2d-画出好看的图形
  2. P1029 栈的基础操作
  3. 多校 HDU - 6614 AND Minimum Spanning Tree (二进制)
  4. dotnet core 隐藏控制台
  5. 【21.00%】【vijos P1018】智破连环阵
  6. poj2826 An Easy Problem?!(计算几何)
  7. 【34.54%】【codeforces 675E】Trains and Statistic
  8. Vue的数据双向绑定和Object.defineProperty()
  9. blink接收器
  10. world 文档中表格旋转180&#176;