提出 #64624657

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define ls(p) (p*2)
#define rs(p) (p*2+1)
const int N=2e5+5,inf=1e9;
int n,m,d,cnt[N],l[N],r[N],ans[N];
int vc[N],sl[N],sr[N],cur[N];
set<int> id;
priority_queue<pair<int,int>> pq[N];// first:l second:id
pair<int,int> calc(int p){
	while(!pq[p].empty()){
		auto [l,id]=pq[p].top();
		if(ans[id]) pq[p].pop();
		else return {-l,id};
	}
	return {inf,0};
}
struct Sgt1{
	pair<int,int> tree[N<<2];
	void build(int p,int l,int r){
		if(l==r){
			tree[p]=calc(l);
			return ;
		}
		int mid=(l+r)/2;
		build(ls(p),l,mid),build(rs(p),mid+1,r);
		tree[p]=min(tree[ls(p)],tree[rs(p)]);
	}
	pair<int,int> find(int p,int l,int r,int cl,int cr){
		if(cl>=l && cr<=r) return tree[p];
		int mid=(cl+cr)/2;
		if(r<=mid) return find(ls(p),l,r,cl,mid);
		if(l>mid) return find(rs(p),l,r,mid+1,cr);
		return min(find(ls(p),l,r,cl,mid),find(rs(p),l,r,mid+1,cr));
	}
	void del(int p,int pos,int l,int r){
		if(l==r){
			tree[p]=calc(pos);
			return ;
		}
		int mid=(l+r)/2;
		if(pos<=mid) del(ls(p),pos,l,mid);
		else del(rs(p),pos,mid+1,r);
		tree[p]=min(tree[ls(p)],tree[rs(p)]);
	}
} sgt;
priority_queue<int> pl[N],pr[N];
inline int calcl(int k){
	while(!pl[k].empty()){
		int p=-pl[k].top();
		if(ans[p]) pl[k].pop();
		else return p;
	}
	return inf;
}
inline int calcr(int k){
	while(!pr[k].empty()){
		int p=-pr[k].top();
		if(ans[p]) pr[k].pop();
		else return p;
	}
	return inf;
}
struct Sgt2{
	int tree[N<<2];
	void build(int p,int l,int r){
		if(l==r){
			tree[p]=calcl(l);
			return ;
		}
		int mid=(l+r)/2;
		build(ls(p),l,mid),build(rs(p),mid+1,r);
		tree[p]=min(tree[ls(p)],tree[rs(p)]);
	}
	int qry(int p,int l,int r,int cl,int cr){
		if(cl>=l && cr<=r) return tree[p];
		int mid=(cl+cr)/2;
		if(r<=mid) return qry(ls(p),l,r,cl,mid);
		if(l>mid) return qry(rs(p),l,r,mid+1,cr);
		return min(qry(ls(p),l,r,cl,mid),qry(rs(p),l,r,mid+1,cr));
	}
	void del(int p,int pos,int l,int r){
		if(l==r){
			tree[p]=calcl(pos);
			return ;
		}
		int mid=(l+r)/2;
		if(pos<=mid) del(ls(p),pos,l,mid);
		else del(rs(p),pos,mid+1,r);
		tree[p]=min(tree[ls(p)],tree[rs(p)]);
	}
} sgtl;
struct Sgt3{
	int tree[N<<2];
	void build(int p,int l,int r){
		if(l==r){
			tree[p]=calcr(l);
			return ;
		}
		int mid=(l+r)/2;
		build(ls(p),l,mid),build(rs(p),mid+1,r);
		tree[p]=min(tree[ls(p)],tree[rs(p)]);
	}
	int qry(int p,int l,int r,int cl,int cr){
		if(cl>=l && cr<=r) return tree[p];
		int mid=(cl+cr)/2;
		if(r<=mid) return qry(ls(p),l,r,cl,mid);
		if(l>mid) return qry(rs(p),l,r,mid+1,cr);
		return min(qry(ls(p),l,r,cl,mid),qry(rs(p),l,r,mid+1,cr));
	}
	void del(int p,int pos,int l,int r){
		if(l==r){
			tree[p]=calcr(pos);
			return ;
		}
		int mid=(l+r)/2;
		if(pos<=mid) del(ls(p),pos,l,mid);
		else del(rs(p),pos,mid+1,r);
		tree[p]=min(tree[ls(p)],tree[rs(p)]);
	}	
} sgtr;
int buildl(int k){
	int cnt=0,sz=0;
	for(int p:id){
		vc[++sz]=p;
		if(sz==k) break;
	}
	sort(vc+1,vc+sz+1,[](int x,int y){ return l[x]>l[y]; });
	for(int i=1;i<=sz;i++){
		if(r[vc[i]]<sl[cnt]){
			sl[++cnt]=l[vc[i]];
		}
	}
	reverse(sl+1,sl+cnt+1);
	sl[cnt+1]=inf;
	return cnt;
}
int buildr(int k){
	int cnt=0,sz=0;
	for(int p:id){
		vc[++sz]=p;
		if(sz==k) break;
	}
	sort(vc+1,vc+sz+1,[](int x,int y){ return r[x]<r[y]; });
	for(int i=1;i<=sz;i++){
		if(l[vc[i]]>sr[cnt]){
			sr[++cnt]=r[vc[i]];
		}
	}
	return cnt;
}
void ers(int x){
	id.erase(x);
	sgt.del(1,r[x],1,n);
}
struct Node1{
	int id;
	friend bool operator<(const Node1& A,const Node1& B){
		if(l[A.id]!=l[B.id]) return l[A.id]>l[B.id];
		return A.id<B.id;
	}
};
struct Node2{
	int id;
	friend bool operator<(const Node2& A,const Node2& B){
		if(r[A.id]!=r[B.id]) return r[A.id]<r[B.id];
		return A.id<B.id;
	}
};
set<Node1> setl;
set<Node2> setr;
void process(int cl,int cr,int col){
	auto [l,id]=sgt.find(1,cr,n,1,n);
	while(l<=cl){
		ans[id]=col,ers(id);
		auto res=sgt.find(1,cr,n,1,n);
		l=res.first,id=res.second;
	}
}
void updater(int id,int col){
	setr.insert({id});
	auto it=setr.find({id});
	int p=upper_bound(sr+1,sr+d+1,r[id])-sr; 
	while(it!=setr.end()){
		if(l[it->id]>sr[p-1]){
			int tmp=r[it->id];
			if(tmp==sr[p]) return ;
			sr[p++]=tmp;
			process(sl[p-1],sr[p-1],col);
		}
		it++;
	}
}
void updatel(int id,int col){
	setl.insert({id});
	auto it=setl.find({id});
	int p=lower_bound(sl+1,sl+d+1,l[id])-sl-1;
	while(it!=setl.end()){
		if(r[it->id]<sl[p+1]){
			int tmp=l[it->id];
			if(tmp==sl[p]) return ;
			sl[p--]=tmp;
			process(sl[p+1],sr[p+1],col);
		}
		it++;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	sr[0]=0,sl[0]=inf;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		cnt[x]++;
	}
	for(int i=1;i<=m;i++) cin>>l[i]>>r[i];
	for(int i=1;i<=m;i++){
		id.insert(i);
		pq[r[i]].push({-l[i],i});
		pl[l[i]].push(-i),pr[r[i]].push(-i);
	}
	sgt.build(1,1,n),sgtl.build(1,1,n),sgtr.build(1,1,n);
	for(int i=n;i>=1;i--){
		if(!cnt[i]) continue;
		int bl=0,br=0,res=-1;
		for(int k=0;(1<<k)<=id.size();k++){
			if(buildl(1<<k)>cnt[i]){
				bl=(1<<(k-1)),br=(1<<k)-1;
				break;
			}
		}
		if(!bl){
			bl=1,br=id.size();
		}
		while(bl<=br){
			int mid=(bl+br)/2;
			if(buildl(mid)<=cnt[i]) bl=mid+1,res=mid;
			else br=mid-1;
		}
		d=buildl(res);
		buildr(res);
		setl.clear(),setr.clear();
		for(int k=1;k<=res;k++){
			setl.insert({vc[k]}),setr.insert({vc[k]});
			ans[vc[k]]=i,ers(vc[k]);
		}
		priority_queue<pair<int,int>> pq;
		for(int k=1;k<=d;k++){
			int cl=sl[k],cr=sr[k];
			process(cl,cr,i);
			cur[k]=min(sgtl.qry(1,cl,cr,1,n),sgtr.qry(1,cl,cr,1,n));
			pq.push({-cur[k],k});
		}
		while(!pq.empty()){
			auto [id,k]=pq.top();
			id*=-1;
			pq.pop();
			if(id>m) break;
			if(!ans[id]){
				if(r[id]>=sl[k] && l[id]<=sr[k]){
					ans[id]=i,ers(id);
					updater(id,i);
					updatel(id,i);					
				}
			}
			else sgtl.del(1,l[id],1,n),sgtr.del(1,r[id],1,n);
			cur[k]=min(sgtl.qry(1,sl[k],sr[k],1,n),sgtr.qry(1,sl[k],sr[k],1,n));
			pq.push({-cur[k],k});
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:228:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::set<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  228 |                 for(int k=0;(1<<k)<=id.size();k++){
      |                             ~~~~~~^~~~~~~~~~~

ジャッジ結果