Submission #583653

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583653	2022-06-25T21:36:02 Z	tutis	Event Hopping (BOI22_events)	C++17	25 / 100	245 ms	524288 KB

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;
	for (int j = 0; j < N; j++)
	{
		if (S[j] >= j)
			continue;
		pair<int, int>mn = { N + 1, N + 1};
		for (int i = S[j]; i < j; i++)
		{
			D[j][i] = 1;
			mn = min(mn, {S[i], i});
		}
		for (int i = 0; i < S[j]; i++)
			D[j][i] = D[mn.second][i] + 1;
	}
	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 {
				int k = D[t][s];
				if (k > N)
					cout << "impossible\n";
				else
					cout << k << "\n";
			}
		}
	}
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	240 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	3 ms	4180 KB	Output is correct
4	Correct	3 ms	4180 KB	Output is correct
5	Correct	3 ms	4180 KB	Output is correct
6	Correct	3 ms	4180 KB	Output is correct
7	Correct	4 ms	4180 KB	Output is correct
8	Correct	4 ms	4180 KB	Output is correct
9	Correct	4 ms	4180 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	3 ms	4180 KB	Output is correct
4	Correct	3 ms	4180 KB	Output is correct
5	Correct	3 ms	4180 KB	Output is correct
6	Correct	3 ms	4180 KB	Output is correct
7	Correct	4 ms	4180 KB	Output is correct
8	Correct	4 ms	4180 KB	Output is correct
9	Correct	4 ms	4180 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	3 ms	4180 KB	Output is correct
13	Correct	4 ms	4180 KB	Output is correct
14	Correct	4 ms	4224 KB	Output is correct
15	Correct	3 ms	4180 KB	Output is correct
16	Correct	5 ms	4180 KB	Output is correct
17	Correct	5 ms	4180 KB	Output is correct
18	Correct	4 ms	4180 KB	Output is correct
19	Correct	91 ms	98752 KB	Output is correct
20	Correct	82 ms	98764 KB	Output is correct
21	Correct	92 ms	99104 KB	Output is correct
22	Correct	96 ms	99048 KB	Output is correct
23	Correct	96 ms	98900 KB	Output is correct
24	Correct	100 ms	98900 KB	Output is correct
25	Correct	81 ms	98536 KB	Output is correct

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	3 ms	4180 KB	Output is correct
4	Correct	3 ms	4180 KB	Output is correct
5	Correct	3 ms	4180 KB	Output is correct
6	Correct	3 ms	4180 KB	Output is correct
7	Correct	4 ms	4180 KB	Output is correct
8	Correct	4 ms	4180 KB	Output is correct
9	Correct	4 ms	4180 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	3 ms	4180 KB	Output is correct
13	Correct	3 ms	4180 KB	Output is correct
14	Correct	4 ms	4180 KB	Output is correct
15	Correct	3 ms	4180 KB	Output is correct
16	Correct	3 ms	4180 KB	Output is correct
17	Correct	4 ms	4180 KB	Output is correct
18	Correct	3 ms	4180 KB	Output is correct
19	Runtime error	216 ms	524288 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	245 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Runtime error	240 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-