2018.09.16 codeforces 1041 C.Coffee Break(双端列)

#include
#define N 200005
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int n,m,d,q[N],ans[N],tot=0,hd,tl;
struct Node{int v,id;}a[N];
inline bool cmp(Node a,Node b){return a.v<b.v;}
int main(){
	n=read(),m=read(),d=read();
	for(int i=1;i<=n;++i)a[i].v=read(),a[i].id=i;
	sort(a+1,a+n+1,cmp);
	hd=1,tl=0;
	q[++tl]=1,ans[a[1].id]=++tot;
	for(int i=2;i<=n;++i){
		if(a[i].v-d-1>=a[q[hd]].v)ans[a[i].id]=ans[a[q[hd]].id],++hd;
		else ans[a[i].id]=++tot;
		q[++tl]=i;
	}
	cout<<tot<<'
';
	for(int i=1;i<=n;++i)cout<<ans[i]<<' ';
	return 0;
}