Submission #1211050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211050		siewjh	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	152 ms	21804 KiB

event2

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXNPT = 200005;
int la[MAXN], ra[MAXN], nxt[MAXNPT][18];
int getamt(int l, int r){
	int ans = 0, curr = l;
	for (int k = 17; k >= 0; k--)
		if (nxt[curr][k] <= r){
			ans += (1 << k);
			curr = nxt[curr][k];
		}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int nums, req; cin >> nums >> req;
	vector<int> disc;
	for (int i = 1; i <= nums; i++){
		cin >> la[i] >> ra[i];
		disc.push_back(la[i]); disc.push_back(ra[i]);
	}
	sort(disc.begin(), disc.end());
	disc.resize(distance(disc.begin(), unique(disc.begin(), disc.end())));
	int dsz = disc.size();
	vector<pair<int, int>> sbl(nums);
	for (int i = 1; i <= nums; i++){
		la[i] = lower_bound(disc.begin(), disc.end(), la[i]) - disc.begin();
		ra[i] = lower_bound(disc.begin(), disc.end(), ra[i]) - disc.begin();
		sbl[i - 1] = {la[i], ra[i]};
	}
	sort(sbl.begin(), sbl.end());
	int lid = nums - 1;
	nxt[dsz - 1][0] = MAXNPT;
	for (int i = dsz - 2; i >= 0; i--){
		int res = nxt[i + 1][0];
		for (; lid >= 0 && sbl[lid].first >= i; lid--) res = min(res, sbl[lid].second);
		nxt[i][0] = res;
	}
	for (int k = 1; k <= 17; k++)
		for (int i = 0; i < dsz; i++){
			if (nxt[i][k - 1] == MAXNPT) nxt[i][k] = MAXNPT;
			else nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
		}
	int cnt = 0, mxans = getamt(0, dsz - 1);
	set<pair<int, int>> rs;
	rs.insert({0, dsz - 1});
	if (mxans < req){
		cout << -1; return 0;
	}
	for (int i = 1; i <= nums && cnt != req; i++){
		int l = la[i], r = ra[i];
		auto it = rs.lower_bound({l + 1, -1});
		if (it == rs.begin()) continue;
		it--;
		if (it->second < r) continue;
		int rl, rr; tie(rl, rr) = *it;
		int nans = mxans - getamt(rl, rr) + getamt(rl, l) + 1 + getamt(r, rr);
		if (nans < req) continue;
		cout << i << '\n';
		cnt++; mxans = nans;
		rs.erase(it);
		if (rl != l) rs.insert({rl, l});
		if (r != rr) rs.insert({r, rr});
	}
}

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