Submission #1089250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089250		ymm	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	49 ms	19804 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;
int from[N];
vector<pii> nxt[N];
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 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,vec.size()) {
		auto [l, r] = vec[i];
		nxt[l].push_back({i, r});
	}
	LoopR (p,0,m) {
		for (auto [_, p2] : nxt[p])
			from[p] = max(from[p], from[p2] + 1);
		from[p] = max(from[p], from[p+1]);
	}
	if (from[0] < k) {
		cerr << "-1\n";
		return 0;
	}
	vector<vector<int>> list(k);
	Loop (i,0,vec.size()) {
		auto [l, r] = vec[i];
		list[min<int>(k-1, from[r])].emplace_back(i);
	}
	vector<int> ans;
	int pnt = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	LoopR (pos,0,k) {
		for (int i : list[pos])
			pq.push(i);
		while (vec[pq.top()].first < pnt)
			pq.pop();
		ans.push_back(pq.top());
		pnt = vec[pq.top()].second;
	}
	for (int i : ans)
		cout << i+1 << '\n';
}

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