Submission #583659

#	Time	Username	Problem	Language	Result	Execution time	Memory
583659		tutis	Event Hopping (BOI22_events)	C++17	100 / 100	111 ms	12108 KiB

events

/*input
8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, Q;
	cin >> N >> Q;
	pair<pair<int, int>, int>A[N];
	for (int i = 0; i < N; i++)
	{
		cin >> A[i].first.second >> A[i].first.first;
		A[i].second = i;
	}
	sort(A, A + N);
	int p[N];
	for (int i = 0; i < N; i++)
		p[A[i].second] = i;
	int S[N], E[N];
	for (int i = 0; i < N; i++)
	{
		S[i] = A[i].first.second;
		E[i] = A[i].first.first;
	}
	for (int i = 0; i < N; i++)
	{
		S[i] = (lower_bound(E, E + N, S[i]) - E);
	}
	// int D[N][N];
	// for (int i = 0; i < N; i++)
	// 	for (int j = 0; j < N; j++)
	// 		D[i][j] = N + 10;
	vector<int>V;
	int pa[N][20];
	for (int j = 0; j < N; j++)
	{
		if (S[j] >= j)
		{
			pa[j][0] = j;
		}
		else
		{
			auto it = lower_bound(V.begin(), V.end(), S[j]);
			assert(it != V.end());
			pa[j][0] = *it;
		}
		for (int i = 1; i < 20; i++)
			pa[j][i] = pa[pa[j][i - 1]][i - 1];
		while (!V.empty() && S[V.back()] >= S[j])
			V.pop_back();
		V.push_back(j);
	}
	while (Q--)
	{
		int s, t;
		cin >> s >> t;
		s = p[s - 1];
		t = p[t - 1];
		if (s == t)
		{
			cout << "0\n";
		}
		else {
			if (A[t].first.second <= A[s].first.first && A[s].first.first <= A[t].first.first)
				cout << "1\n";
			else {
				if (s >= t)
				{
					cout << "impossible\n";
					continue;
				}
				int a = 1;
				for (int i = 19; i >= 0; i--)
					if (s < S[pa[t][i]])
					{
						t = pa[t][i];
						a += (1 << i);
					}
				if (s < S[t])
				{
					t = pa[t][0];
					a++;
				}
				if (s >= S[t])
				{
					cout << a << "\n";
				}
				else
				{
					cout << "impossible\n";
				}
				// int k = D[t][s];
				// if (k > N)
				// 	cout << "impossible\n";
				// else
				// 	cout << k << "\n";
			}
		}
	}
}

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