Submission #906680

#	Time	Username	Problem	Language	Result	Execution time	Memory
906680		NK_	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	318 ms	44460 KiB

event2

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define s second
#define f first

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;


const int INF = 1e9 + 10;
const int LG = 19;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K; cin >> N >> K;

	vi L(N), R(N); for(int i = 0; i < N; i++) {
		cin >> L[i] >> R[i];
	}

	int M = -1;
	{	
		map<int, int> mp; int cur = 0;
		for(auto& x : L) mp[x]++;
		for(auto& x : R) mp[x]++;
		for(auto& x : mp) x.second = cur++;
		for(auto& x : L) x = mp[x];
		for(auto& x : R) x = mp[x];
		M = cur;
	}

	V<vi> E(M);
	for(int i = 0; i < N; i++) E[L[i]].pb(i);

	multiset<int> S = {M}; V<vi> nxt(M+1, vi(LG, M));
	for(int t = M - 1; t >= 0; t--) {	
	
		for(auto& i : E[t]) S.insert(R[i]);

		nxt[t][0] = *begin(S);
		// cout << nxt[t][0] << endl;

		for(int i = 1; i < LG; i++) nxt[t][i] = nxt[nxt[t][i-1]][i-1];
	}

	auto qry = [&](int l, int r) {
		if (l > r) return -INF;
		int ans = 0;
		for(int i = LG - 1; i >= 0; i--) {
			if (nxt[l][i] <= r) ans += (1 << i), l = nxt[l][i];
		}
		return ans;
	};


	vi ans;

	// L.pb(0); R.pb(0);
	// L.pb(M - 1); R.pb(M - 1);

	set<pi> ord = {mp(0, -INF), mp(M - 1, INF)};

	int have = qry(0, M - 1);

	if (have < K) {
		cout << -1 << nl;
		exit(0-0);
	}

	// cout << "HAVE: " << have << endl;
	for(int i = 0; i < N; i++) {
		auto it = ord.lower_bound(mp(L[i], INF));

		int bef = (*prev(it)).s, aft = (*it).s;

		int befr = (bef == -INF ? 0 : R[bef]);
		int aftl = (aft == INF ? M - 1 : L[aft]);

		// cout << i << " " << L[i] << " " << R[i] << endl;
		// cout << befr << " " << aftl << endl;

		int without = qry(befr, aftl);
		int with = qry(befr, L[i]) + 1 + qry(R[i], aftl);

		int lost = without - with;
		if ((have - lost) >= K) {
			// cout << "ADDING: " << i << " => " << have << endl;
			have -= lost, ans.pb(i);
			ord.insert(mp(L[i], i));
		}

		if (sz(ans) == K) break;
	}

	for(auto& x : ans) cout << x + 1 << nl;

	exit(0-0);
} 

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