Submission #583652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583652	2022-06-25T21:30:49 Z	tutis	Event Hopping (BOI22_events)	C++17	25 / 100	226 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;
		int id1 = S[j];
		int id2 = j - 1;
		int t = 1;
		while (id1 <= id2)
		{
			int mn = N + 1;
			for (int i = id1; i <= id2; i++)
			{
				D[i][j] = t;
				mn = min(mn, S[i]);
			}
			t++;
			id2 = id1 - 1;
			id1 = mn;
		}
	}
	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	220 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	5 ms	4252 KB	Output is correct
4	Correct	4 ms	4180 KB	Output is correct
5	Correct	6 ms	4256 KB	Output is correct
6	Correct	3 ms	4180 KB	Output is correct
7	Correct	5 ms	4244 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	5 ms	4252 KB	Output is correct
4	Correct	4 ms	4180 KB	Output is correct
5	Correct	6 ms	4256 KB	Output is correct
6	Correct	3 ms	4180 KB	Output is correct
7	Correct	5 ms	4244 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	0 ms	212 KB	Output is correct
12	Correct	6 ms	4180 KB	Output is correct
13	Correct	4 ms	4180 KB	Output is correct
14	Correct	6 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	3 ms	4248 KB	Output is correct
18	Correct	5 ms	4180 KB	Output is correct
19	Correct	195 ms	99068 KB	Output is correct
20	Correct	172 ms	98816 KB	Output is correct
21	Correct	184 ms	99032 KB	Output is correct
22	Correct	142 ms	99200 KB	Output is correct
23	Correct	155 ms	98976 KB	Output is correct
24	Correct	198 ms	99036 KB	Output is correct
25	Correct	161 ms	98572 KB	Output is correct

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	5 ms	4252 KB	Output is correct
4	Correct	4 ms	4180 KB	Output is correct
5	Correct	6 ms	4256 KB	Output is correct
6	Correct	3 ms	4180 KB	Output is correct
7	Correct	5 ms	4244 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	0 ms	212 KB	Output is correct
12	Correct	6 ms	4180 KB	Output is correct
13	Correct	4 ms	4248 KB	Output is correct
14	Correct	6 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	3 ms	4180 KB	Output is correct
18	Correct	4 ms	4180 KB	Output is correct
19	Runtime error	222 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	226 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	220 ms	524288 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-