Submission #1089437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089437		ymm	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	104 ms	26960 KiB

event2

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 20;
int go[N][lg];
vector<int *> cmper;
int n, m, k;

void compress()
{
	sort(cmper.begin(), cmper.end(), [](int *p, int *q) {
		return *p < *q;
	});
	m = 0;
	for (size_t i = 0; i < cmper.size();) {
		size_t j = i + 1;
		while (j < cmper.size() && *cmper[i] == *cmper[j])
			j++;
		for (auto k = i; k < j; k++)
			*cmper[k] = m;
		m++;
		i = j;
	}
}

int calc(int l, int r)
{
	int ans = 0;
	LoopR (i,0,lg) {
		if (go[l][i] <= r) {
			ans += 1 << i;
			l = go[l][i];
		}
	}
	return ans;
}

vector<int> solve(const vector<pii> &vec)
{
	int sum = calc(0, m);
	struct Inter {
		int l, r, sum;
		bool operator<(const Inter &i) const {
			return l < i.l;
		}
	};
	set<Inter> s;
	s.insert({0, m, sum});

	vector<int> ans;
	Loop (i,0,vec.size()) {
		auto [l, r] = vec[i];
		auto it = --s.upper_bound(Inter{l, INT_MAX, INT_MAX});
		if (!(it->l <= l && r <= it->r))
			continue;
		int vl = calc(it->l, l);
		int vr = calc(r, it->r);
		if (sum - it->sum + vl + vr + 1 + (ll)ans.size() < k)
			continue;
		//cerr << "picked " << i << ": " << l << ' ' << r << " inter " << it->l << ", " << it->r << ", " << it->sum
		//	<< " left " << vl << " right " << vr << " new sum " << sum - it->sum + vl + vr << '\n';
		sum = sum - it->sum + vl + vr;
		auto clone = *it;
		s.erase(it);
		s.insert(Inter{clone.l, l, vl});
		s.insert(Inter{r, clone.r, vr});
		ans.push_back(i);
	}
	assert((ll)ans.size() >= k);
	ans.resize(k);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k;
	vector<pii> vec;
	Loop (i,0,n) {
		int x, y;
		cin >> x >> y;
		vec.emplace_back(x, y);
	}

	for (auto &[l, r] : vec) {
		cmper.push_back(&l);
		cmper.push_back(&r);
	}
	compress();

	Loop (i,0,m+2) Loop (j,0,lg)
		go[i][j] = m+1;
	for (auto [l, r] : vec)
		go[l][0] = min(go[l][0], r);
	LoopR (i,0,m+1)
		go[i][0] = min(go[i][0], go[i+1][0]);

	Loop (j,0,lg-1) Loop (i,0,m)
		go[i][j+1] = go[go[i][j]][j];

	if (calc(0, m) < k) {
		cout << "-1\n";
		return 0;
	}

	auto ans = solve(vec);
	for (int i : ans)
		cout << i+1 << '\n';
}

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