Submission #3050433

---

Source Code Expand

#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 500005;
struct Edge{
	int to,next;
}e[MAXN<<1];
int p[MAXN],q[MAXN],n,head[MAXN],in[MAXN],ord[MAXN],val[MAXN],k;
set<int>ele;
typedef set<int>::iterator SI;
priority_queue<int>pq;
int mx[MAXN<<2];
int ql,qr,qval,qpos;
void update(int i,int l,int r)
{
	if(l==r)return void(mx[i]=qval);
	int mid=(l+r)>>1,lc=i<<1,rc=lc|1;
	if(qpos<=mid)update(lc,l,mid);
	else update(rc,mid+1,r);
	mx[i]=max(mx[lc],mx[rc]);
}
int query(int i,int l,int r)
{
//	cout<<i<<" "<<l<<" "<<r<<endl;
	if(l>=ql&&r<=qr)return mx[i];
	int mid=(l+r)>>1,lc=i<<1,rc=lc|1;
	if(qr<=mid)return query(lc,l,mid);
	else if(ql>mid)return query(rc,mid+1,r);
	else return max(query(lc,l,mid),query(rc,mid+1,r));
}
int cnt;
inline void insert(int u,int v)
{
	e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%d",p+i),q[p[i]]=i;
	for(int i=1;i<=n;++i){
		ql=max(q[i]-k+1,1),qr=q[i];
//		cout<<ql<<" "<<qr<<endl;
		int x=query(1,1,n);
		if(x)insert(q[i],q[x]),++in[q[x]];
		ql=q[i],qr=min(q[i]+k-1,n);
//		cout<<ql<<" "<<qr<<endl;
		x=query(1,1,n);
		if(x)insert(q[i],q[x]),++in[q[x]];
		qpos=q[i],qval=i;
//		cout<<qpos<<" "<<qval<<endl;
		update(1,1,n);
	}
	for(int i=1;i<=n;++i)
		if(!in[i])pq.push(i);
	for(int i=n;i;--i){
		ord[i]=pq.top();
		pq.pop();
		for(int j=head[ord[i]];j;j=e[j].next){
			int v=e[j].to;
			if(!--in[v]){
				pq.push(v);				
			}
		}
	}
	for(int i=1;i<=n;++i)val[ord[i]]=i;
	for(int i=1;i<=n;++i)printf("%d\n",val[i]);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
./Main.cpp:42:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;++i)scanf("%d",p+i),q[p[i]]=i;
                                                ^

Judge Result