Submission #576901

#	Time	Username	Problem	Language	Result	Execution time	Memory
576901		aryan12	Event Hopping (BOI22_events)	C++17	100 / 100	460 ms	43672 KiB

events

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5, INF = 1e15;
int s[N], e[N];
int dp[20][N];
vector<pair<int, int> > seg(N * 8, {INF, -1});

void update(int l, int r, int pos, int qpos, pair<int, int> qval)
{
	if(l == r)
	{
		seg[pos] = min(seg[pos], qval);
		return;
	}
	int mid = (l + r) >> 1;
	if(qpos <= mid) update(l, mid, pos * 2, qpos, qval);
	else 			update(mid + 1, r, pos * 2 + 1, qpos, qval);
	seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
}

pair<int, int> query(int l, int r, int pos, int ql, int qr)
{
	if(ql > r || l > qr) return {INF, -1};
	if(ql <= l && r <= qr) return seg[pos];
	int mid = (l + r) >> 1;
	return min(query(l, mid, pos * 2, ql, qr), query(mid + 1, r, pos * 2 + 1, ql, qr));
}

void Solve() 
{
	int n, q;
	cin >> n >> q;
	map<int, int> cc;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i] >> e[i];
		cc[s[i]]++;
		cc[e[i]]++;
	}
	int cnt = 0;
	for(auto i: cc)
	{
		cc[i.first] = ++cnt;
	}
	for(int i = 1; i <= n; i++)
	{
		s[i] = cc[s[i]];
		e[i] = cc[e[i]];
		update(1, cnt, 1, e[i], {s[i], i});
	}
	for(int i = 1; i <= n; i++)
	{
		pair<int, int> res = query(1, cnt, 1, s[i], e[i]);
		if(res.first >= s[i]) dp[0][i] = -1;
		else 				  dp[0][i] = res.second;
	}
	for(int i = 1; i <= 19; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(dp[i - 1][j] == -1) dp[i][j] = -1;
			else 				   dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
	while(q--)
	{
		int qs, qe;
		cin >> qs >> qe;
		if(qs == qe)
		{
			cout << "0\n";
			continue;
		}
		if(e[qs] > e[qe])
		{
			cout << "impossible\n";
			continue;
		}
		if(s[qe] <= e[qs] && e[qs] <= e[qe])
		{
			cout << "1\n";
			continue;
		}
		int cur = qe, ans = 1;
		for(int i = 19; i >= 0; i--)
		{
			if(dp[i][cur] != -1 && s[dp[i][cur]] > e[qs])
			{
				cur = dp[i][cur];
				ans += (1 << i);
			}
		}
		if(dp[0][cur] == -1)
		{
			cout << "impossible\n";
		}
		else
		{
			cout << ans + 1 << "\n";
		}
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30