Submission #386312

#	Time	Username	Problem	Language	Result	Execution time	Memory
386312		myrcella	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	348 ms	34168 KiB

event2

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn=2e5+10;

int n,m;
map <int,int> mp;
pii seg[maxn];
int suf[maxn],nxt[maxn][20];
vector <int> ans;
set <pii> s;

int solve(int l,int r) {
	int res=0;
	for (int i=19;i>=0;i--) {
		if (nxt[l][i]<=r) {
			res+=(1<<i);
			l=nxt[l][i];
		}
	}
	return res;
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie();
	cin>>n>>m;
	rep(i,0,n) cin>>seg[i].fi>>seg[i].se,mp[seg[i].fi]=mp[seg[i].se]=1;
	int tot=0;
	for (auto it=mp.begin();it!=mp.end();it++) it->se=tot++;
	memset(suf,inf,sizeof(suf));
	memset(nxt,inf,sizeof(nxt));
	rep(i,0,n) seg[i]=MP(mp[seg[i].fi],mp[seg[i].se]),suf[seg[i].fi]=min(seg[i].se,suf[seg[i].fi]);
	for (int i=tot-1;i>=0;i--) suf[i]=min(suf[i+1],suf[i]);
	for (int i=tot-1;i>=0;i--) {
		nxt[i][0]=suf[i];
		for (int j=1;nxt[i][j-1]<maxn;j++) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	}
	s.insert(MP(0,tot-1));
	int cur=solve(0,tot-1);
	if (cur<m) {
		cout<<-1;
		return 0;
	}
	rep(i,0,n) {
		int l=seg[i].fi,r=seg[i].se;
		auto it=s.upper_bound(MP(l,mod));
		if (it==s.begin()) continue;
		it--;
		if ((*it).se<r) continue;
		int tmp=cur-solve((*it).fi,(*it).se)+solve((*it).fi,l)+solve(r,(*it).se)+1;
		if (tmp>=m) {
			s.insert(MP((*it).fi,l));
			s.insert(MP(r,(*it).se));
			s.erase(*it);
			cur=tmp;
			ans.pb(i+1);
			if (SZ(ans)==m) break;
		}
	}
	for (int &i:ans) cout<<i<<"\n";
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61