Submission #783695

#	Time	Username	Problem	Language	Result	Execution time	Memory
783695		Abrar_Al_Samit	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	491 ms	45880 KiB

event2

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



const int nax = 2e5 + 3;
const int lg = 20;

int to[nax];
int jt[nax][lg];

int jump(int i, int j) {
	if(jt[i][j]!=-1) return jt[i][j];

	if(j==0) return jt[i][j] = to[i];

	return jt[i][j] = jump(jump(i, j-1), j-1);
}
int get_ans(int l, int r) {
	int ret = 0;
	for(int i=lg-1; i>=0; --i) {
		if(jump(r, i)>=l) {
			ret |= 1<<i;
			r = jump(r, i);
		}
	}
	return ret;
}
void PlayGround() {
	int n, k;
	cin>>n>>k;

	map<pair<int,int>, int>rg;
	map<int,int>h;

	for(int i=1; i<=n; ++i) {
		int l, r;
		cin>>l>>r;

		int cr = rg[{l, r}];
		if(!cr) {
			rg[{l, r}] = i;
			h[l] = h[r] = 1;
		}
	}
	int cm = 1;

	for(auto &it : h) {
		it.second = cm++;
	}

	for(auto &it : rg) {
		auto [l, r] = it.first;

		to[h[r]] = max(to[h[r]], h[l]);
	}

	for(int i=1; i<=2 * n + 1; ++i) {
		to[i] = max(to[i], to[i-1]);
	}


	memset(jt, -1, sizeof jt);

	map<int, pair<int,int>>id_to_rg;
	for(auto it : rg) {
		id_to_rg[it.second] = it.first;
	}


	int cur = get_ans(1, 2*n + 1);

	if(cur < k) {
		cout<<"-1\n";
		return;
	}

	set<pair<int,int>>alive = {{2 * n + 1, 1}};

	vector<int>ans;
	for(auto it : id_to_rg) {
		if(ans.size()==k) break;

		auto [l, r] = it.second;
		l = h[l], r = h[r];

		auto rel = *alive.lower_bound(make_pair(r, -1));

		if(rel.second<=l) { //can take
			int new_ans = cur - get_ans(rel.second, rel.first) 
				+ get_ans(rel.second, l) + get_ans(r, rel.first);

			if(new_ans + ans.size() + 1 >= k) {
				ans.push_back(it.first);
				cur = new_ans;

				alive.erase(rel);
				alive.insert({l, rel.second});
				alive.insert({rel.first, r});
			}
		}
	}
	for(int x : ans) {
		cout<<x<<'\n';
	}


	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'void PlayGround()':
event2.cpp:82:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   if(ans.size()==k) break;
      |      ~~~~~~~~~~^~~
event2.cpp:93:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |    if(new_ans + ans.size() + 1 >= k) {
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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