Submission #417282

#	Time	Username	Problem	Language	Result	Execution time	Memory
417282		pavement	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	609 ms	304636 KiB

event2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, K, curr, L[500005], R[500005], dep[500005], anc[500005][25];
bool in[500005];
ii mx[500005], prec[500005];
set<ii> untaken;
vector<int> v, adj[500005];
vector<ii> vec[500005];
gp_hash_table<int, int> chc[500005];

void dfs(int n, int e = -1) {
	anc[n][0] = e;
	for (int i = 1; i <= 17; i++)
		if (anc[n][i - 1] != -1) anc[n][i] = anc[anc[n][i - 1]][i - 1];
	for (auto u : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		dfs(u, n);
	}
}

int get(int l, int r) {
	if (chc[l].find(r) != chc[l].end()) return chc[l][r];
	auto tmp = prec[l];
	if (tmp.second == LLONG_MAX) return 0;
	int curr = tmp.second;
	if (R[curr] > r) return 0;
	for (int i = 17; i >= 0; i--)
		if (anc[curr][i] != -1 && R[anc[curr][i]] <= r) curr = anc[curr][i];
	return chc[l][r] = dep[mx[l].second] - dep[curr] + 1;
}

int forceadd(int x, bool b = 0) {
	auto it = untaken.lower_bound(mp(R[x], 0ll));
	if (it == untaken.begin()) return -1;
	--it;
	if (it->first <= L[x] && R[x] <= it->second) {
		if (b == 1) {
			untaken.emplace(it->first, L[x]);
			untaken.emplace(R[x], it->second);
			untaken.erase(it);
		}
		int tmp = 1 + curr + -get(it->first, it->second) + get(it->first, L[x]) + get(R[x], it->second);
		if (b) curr = tmp;
		return tmp;
	} else return -1;
}

main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> L[i] >> R[i], v.pb(L[i]), v.pb(R[i]);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for (int i = 1; i <= N; i++) {
		L[i] = lower_bound(v.begin(), v.end(), L[i]) - v.begin() + 1;
		R[i] = lower_bound(v.begin(), v.end(), R[i]) - v.begin() + 1;
		vec[L[i]].eb(R[i], i);
	}
	for (int i = 2 * N; i >= 1; i--) {
		prec[i] = mp(LLONG_MAX, LLONG_MAX);
		if (i < 2 * N) prec[i] = prec[i + 1];
		for (auto j : vec[i]) prec[i] = min(prec[i], j);
	}
	for (int i = 1; i <= N; i++) {
		auto tmp = prec[R[i]];
		if (tmp.second != LLONG_MAX) {
			assert(R[i] <= L[tmp.second]);
			adj[tmp.second].pb(i);
			in[i] = 1;
		}
	}
	for (int i = 1; i <= N; i++)
		if (!in[i])
			dfs(i);
	for (int i = 1; i <= 2 * N; i++)
		mx[L[i]] = max(mx[L[i]], mp(dep[i] + 1, i));
	for (int i = 2 * N; i >= 1; i--) mx[i] = max(mx[i], mx[i + 1]);
	untaken.emplace(1, 2 * N);
	curr = get(1, 2 * N);
	if (curr < K) return cout << "-1\n", 0;
	for (int i = 1, cnt = 0; i <= N; i++) {
		int x = forceadd(i);
		if (x >= K) {
			cout << i << '\n';
			cnt++;
			if (cnt == K) return 0;
			forceadd(i, 1);
		}
	}
}

Compilation message (stderr)

event2.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main() {
      | ^~~~

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