WA On #126 求条

#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int read(){
	int sum=0,fg=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') fg=-1;
		c=getchar();
	}
	while('0'<=c&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*fg;
}

struct seg{
	int l,r;
	seg(int _l=0,int _r=0){
		l=_l,r=_r;
	}
	bool operator<(const seg &o) const{
		return r<o.l;
	}
} a[N];

void init();
void solve();

int main(){
	init();
	solve();
	return 0;
}

int n,m,k,b[N<<1],f[19][N<<1];

void init(){
	n=read(),k=read();
	for(int i=1;i<=n;++i){
		b[++m]=a[i].l=read();
		b[++m]=a[i].r=read();
	}
	sort(b+1,b+m+1);
	m=unique(b+1,b+m+1)-(b+1);
	for(int i=1;i<=n;++i){
		a[i].l=lower_bound(b+1,b+m+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+m+1,a[i].r)-b;
	}
	for(int i=0;i<19;++i)
		for(int j=1;j<=m+5;++j)
			f[i][j]=m+5;
	for(int i=1;i<=n;++i) f[0][a[i].l]=a[i].r;
	for(int i=m;i;--i) f[0][i]=min(f[0][i],f[0][i+1]);
	for(int i=1;i<19;++i)
		for(int j=1;j<=m;++j)
			if(f[i-1][j]<=m)
				f[i][j]=f[i-1][f[i-1][j]];
}

int query(int l,int r){
	int res=0,now=l;
	for(int i=18;~i;--i)
		if(f[i][now]<=r){
			now=f[i][now];
			res+=1<<i;
		}
	return res;
}

void solve(){
	vector<int> res;
	set<seg> s;
	s.insert(seg(1,m));
	int cnt=query(1,m);
	for(int i=1;i<=n;++i){
		set<seg>::iterator it=s.find(a[i]);
		if(res.size()==k) break;
		if(it==s.end()) continue;
		int l=it->l,r=it->r;
		if(a[i].l<l||r<a[i].r) continue;
		int now=cnt-query(l,r)+query(l,a[i].l)+query(a[i].r,r);
		if(now>=k-res.size()-1){
			cnt=now;
			res.push_back(i);
			s.erase(it);
			s.insert(seg(l,a[i].l));
			s.insert(seg(a[i].r,r));
		}
	}
	if(res.size()<k) puts("-1");
	else for(int i: res) printf("%d\n",i);
}