Submission #1172586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172586		jj_master	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	243 ms	42276 KiB

event2

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

int n, k;
int a[200001], b[200001];
int ma = 0;
vector<int> pre[400001];
int re[400001][9];
int mi;

int cal(int a, int b) 
{
	int xx = mi;
	if(a > 0) {
		xx = re[a - 1][0];
	}
	if(xx > b) {
		return 0;
	}
	int ans2 = 1;
	for(int j = 17; j >= 0; j--) {
		int cot;
		if(j % 2 == 0) {
			cot = re[xx][j / 2];
		} else {
			cot = re[re[xx][(j / 2)]][(j / 2)];
		}
		if(cot <= b) {
			xx = cot;
			ans2 += (1 << j);
		}
	}
	return ans2;
}

void sol()
{
	cin >> n >> k;
	map<int, int> ss3;
	mi = 2 * n;
	for(int i = 0 ; i < n; i++) {
		cin >> a[i] >> b[i];
		a[i] *= 2;
		a[i] += 1;
		b[i] *= 2;
		ss3[a[i]]++;
		ss3[b[i]]++;
	}
	int ind = -1;
	map<int, int> tt;
	for(auto j : ss3) {
		ind++;
		tt[j.first] = ind;
	}
	for(int i = 0; i < n; i++) {
		a[i] = tt[a[i]];
		ma = max(ma, a[i]);
		b[i] = tt[b[i]];
		pre[a[i]].push_back(b[i]);
	}
	for(int i = 2 * n - 1; i >= 0; i--) {
		re[i][0] = mi;
		for(auto j : pre[i]) {
			mi = min (mi, j);
		}
	}
	for(int i = 0; i < 2 * n; i++) {
		pre[i].clear();
	}
	for(int i = 0; i < 9; i++) {
		re[2 * n][i] = 2 * n;
	}
	for(int j = 1; j < 9; j++) {
		for(int i = 0; i < 2 * n; i++) {
			re[i][j] = re[i][j - 1];
			for(int k = 0; k < 3; k++) {
				re[i][j] = re[re[i][j]][j - 1];
			}
		}
	}
	int cur = cal(0, 2 * n - 1);
	if(cur < k) {
		cout << -1 << "\n";
	}
	set<pair<int, int>> ss;
	ss.insert({0, 2 * n - 1});
	vector<int> ans;
	for(int i = 0;i < n; i++) {
		if(ans.size() == k) {
			break;
		}
		auto j = ss.upper_bound({a[i], 2*n});
		if(j == ss.begin()) {
			continue;
		}
		j--;
		pair<int, int> no=*j;
		if((a[i] >= no.first && b[i] <= no.second)) {
			int cot = cur - cal(no.first, no.second);
			if(no.first < a[i]) {
				cot += cal(no.first, a[i] - 1);
			}
			if(no.second > b[i]) {
				cot += cal(b[i] + 1, no.second);
			}
			cot += 1;
			if(cot >= k) {
				cur = cot;
				ans.push_back(i);
				ss.erase(no);
				if(no.first < a[i]) {
					ss.insert({no.first, a[i] - 1});
				}
				if(no.second > b[i]) { 
					ss.insert({b[i] + 1, no.second});
				}
			}
		} else {
			continue;
		}
	}
	for(auto j : ans){
		cout<< j + 1 << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	sol();
	return 0;
}

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