Submission #583650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583650	2022-06-25T21:23:46 Z	tutis	Event Hopping (BOI22_events)	C++17	10 / 100	1500 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++)
	{
		for (int i = S[j]; i < j; i++)
		{
			D[i][j] = 1;
		}
	}
	for (int i = N - 1; i >= 0; i--)
	{
		for (int j = i + 1; j < N; j++)
		{
			for (int k = i + 1; k < j; k++)
				D[i][j] = min(D[i][j], D[i][k] + D[k][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 {
				int k = D[s][t];
				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	216 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	272 ms	4232 KB	Output is correct
4	Correct	259 ms	4228 KB	Output is correct
5	Correct	283 ms	4232 KB	Output is correct
6	Correct	264 ms	4232 KB	Output is correct
7	Correct	255 ms	4228 KB	Output is correct
8	Correct	271 ms	4240 KB	Output is correct
9	Correct	267 ms	4232 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	272 ms	4232 KB	Output is correct
4	Correct	259 ms	4228 KB	Output is correct
5	Correct	283 ms	4232 KB	Output is correct
6	Correct	264 ms	4232 KB	Output is correct
7	Correct	255 ms	4228 KB	Output is correct
8	Correct	271 ms	4240 KB	Output is correct
9	Correct	267 ms	4232 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	250 ms	4236 KB	Output is correct
13	Correct	279 ms	4236 KB	Output is correct
14	Correct	263 ms	4232 KB	Output is correct
15	Correct	300 ms	4232 KB	Output is correct
16	Correct	261 ms	4180 KB	Output is correct
17	Correct	265 ms	4232 KB	Output is correct
18	Correct	268 ms	4232 KB	Output is correct
19	Execution timed out	1591 ms	98244 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	272 ms	4232 KB	Output is correct
4	Correct	259 ms	4228 KB	Output is correct
5	Correct	283 ms	4232 KB	Output is correct
6	Correct	264 ms	4232 KB	Output is correct
7	Correct	255 ms	4228 KB	Output is correct
8	Correct	271 ms	4240 KB	Output is correct
9	Correct	267 ms	4232 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	273 ms	4236 KB	Output is correct
13	Correct	278 ms	4180 KB	Output is correct
14	Correct	276 ms	4180 KB	Output is correct
15	Correct	267 ms	4180 KB	Output is correct
16	Correct	263 ms	4228 KB	Output is correct
17	Correct	265 ms	4300 KB	Output is correct
18	Correct	255 ms	4180 KB	Output is correct
19	Runtime error	215 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	216 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	216 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-