oj.uz

Submission #745896

# Submission time Handle Problem Language Result Execution time Memory
745896 2023-05-21T09:26:02 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 86 ms 13888 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct event {
	int st, en, id;
};

const int maxn = 100010;
int nxt[maxn][20];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<event> e(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> e[i].st >> e[i].en;
		e[i].id = i;
	}
	e.push_back({ (int)1e9+1, (int)1e9 + 1 });
	for (int i = 0; i < 20; i++) {
		nxt[n + 1][i] = n + 1;
	}
	vector<int> pos(n + 1);
	sort(e.begin()+1, e.end(), [](event& a, event& b) {return a.en < b.en || (a.en==b.en && a.st < b.st); });
	int mn = n + 1;
	for (int i = n; i > 0; i--) {
		pos[e[i].id] = i;
		/*int l = i, r = n + 2;
		while (l + 1 < r) {
			int m = (l + r) / 2;
			if (e[m].st <= e[i].en)l = m;
			else r = m;
		}*/
		nxt[i][0] = (e[mn].st <= e[i].en ? mn : i);
		for (int j = 1; j < 20; j++) {
			nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
		}
		if (e[i].st < e[mn].st)mn = i;
	}
	for (int i = 0; i < q; i++) {
		int s, E;
		cin >> s >> E;
		s = pos[s];
		E = pos[E];
		if (E == s) {
			cout << "0\n";
			continue;
		}
		if (e[s].en == e[E].en) {
			cout << "1\n";
			continue;
		}
		if (E < s) {
			cout << "impossible\n";
			continue;
		}
		int ans = 0;
		for (int i = 19; i >= 0; i--) {
			if (nxt[s][i] < E) {
				ans += (1 << i);
				s = nxt[s][i];
			}
		}
		if (nxt[s][0] != E) {
			cout << "impossible\n";
			continue;
		}
		cout << ans + 1 << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 62 ms 10208 KB Output is correct
3 Correct 64 ms 10292 KB Output is correct
4 Correct 66 ms 10240 KB Output is correct
5 Correct 62 ms 10308 KB Output is correct
6 Correct 66 ms 10276 KB Output is correct
7 Correct 65 ms 10404 KB Output is correct
8 Correct 65 ms 13876 KB Output is correct
9 Correct 61 ms 13888 KB Output is correct
10 Correct 80 ms 13756 KB Output is correct
11 Correct 79 ms 13880 KB Output is correct
12 Correct 52 ms 13244 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10232 KB Output is correct
2 Correct 64 ms 10224 KB Output is correct
3 Correct 66 ms 10224 KB Output is correct
4 Correct 58 ms 10864 KB Output is correct
5 Correct 75 ms 10636 KB Output is correct
6 Incorrect 86 ms 10580 KB Output isn't correct
7 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 Correct 62 ms 10208 KB Output is correct
3 Correct 64 ms 10292 KB Output is correct
4 Correct 66 ms 10240 KB Output is correct
5 Correct 62 ms 10308 KB Output is correct
6 Correct 66 ms 10276 KB Output is correct
7 Correct 65 ms 10404 KB Output is correct
8 Correct 65 ms 13876 KB Output is correct
9 Correct 61 ms 13888 KB Output is correct
10 Correct 80 ms 13756 KB Output is correct
11 Correct 79 ms 13880 KB Output is correct
12 Correct 52 ms 13244 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -