oj.uz

Submission #713527

# Submission time Handle Problem Language Result Execution time Memory
713527 2023-03-22T11:34:33 Z HamletPetrosyan Event Hopping (BOI22_events) C++17
25 / 100
 268 ms 23036 KB 
#include <bits/stdc++.h>
using namespace std;

#define len(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define fr first
#define sc second

const int INF = 1e9;
const int N = 1e5 + 5, lN = 18;

int n, q;
pii a[N];
int par[N][lN];

vector<int> temp, ind;
map<int, int> mp;

pii t[4 * N];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v] = {INF, -1};
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v + 0, tl, tm + 0);
	build(2 * v + 1, tm + 1, tr);
	t[v] = {INF, -1};
}

void update(int v, int tl, int tr, int ind, int val, int i){
	if(tl == tr){
		t[v] = min(t[v], {val, i});
		return;
	}
	int tm = (tl + tr) / 2;
	if(ind <= tm) update(2 * v + 0, tl, tm + 0, ind, val, i);
	else update(2 * v + 1, tm + 1, tr, ind, val, i);
	t[v] = min(t[2 * v + 0], t[2 * v + 1]);
}

pii get(int v, int tl, int tr, int l, int r){
	if(l > r) return (pii){INF, -1};
	if(tl == l && tr == r) return t[v];
	int tm = (tl + tr) / 2;
	return min(get(2 * v + 0, tl, tm + 0, l, min(r, tm + 0)),
			   get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;
	for(int i = 0; i < n; i++){
		cin >> a[i].fr >> a[i].sc;
		temp.push_back(a[i].fr);
		temp.push_back(a[i].sc);
		ind.push_back(i);
	}
	sort(all(temp));
	sort(all(ind), [](int i, int j){ return a[i] < a[j]; });

	int last = -1, cnt = 0;
	for(int i = 0; i < len(temp); i++){
		if(temp[i] == last) continue;
		cnt++;
		last = temp[i];
		mp[temp[i]] = cnt;
	}

	build(1, 1, cnt);
	for(int i = 0; i < n; i++){
		a[i].fr = mp[a[i].fr];
		a[i].sc = mp[a[i].sc];
		update(1, 1, cnt, a[i].sc, a[i].fr, i);
	}

	for(int i = 0; i < n; i++){
		pii h = get(1, 1, cnt, a[i].fr, a[i].sc);
		par[i][0] = (h.fr >= a[i].fr ? -1 : h.sc);
	}
	for(auto i : ind){
		for(int j = 1; j < lN; j++){
			par[i][j] = (par[i][j - 1] == -1 ? -1 : par[par[i][j - 1]][j - 1]);
		}
	}

	int x, y;
	while(q--){
		cin >> x >> y;
		x--, y--;
		if(x == y){
			cout << "0\n";
			continue;
		}
		if(a[x].sc > a[y].sc){
			cout << "impossible\n";
			continue;
		}
		if(a[x].sc >= a[y].fr){
			cout << "1\n";
			continue;
		}

		int ans = 2, now = y;
		for(int i = lN - 1; i >= 0; i--){
			if(par[now][i] == -1) continue;
			if(a[par[now][i]].fr <= a[x].sc) continue;
			ans += (1 << i);
			now = par[now][i];
		}
		if(par[now][0] == -1 || a[par[now][0]].fr > a[x].sc){
			cout << "impossible\n";
			continue;
		}
		cout << ans << "\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 186 ms 16612 KB Output is correct
3 Correct 196 ms 16608 KB Output is correct
4 Correct 250 ms 16656 KB Output is correct
5 Correct 201 ms 17304 KB Output is correct
6 Correct 213 ms 17772 KB Output is correct
7 Correct 208 ms 17820 KB Output is correct
8 Correct 215 ms 22948 KB Output is correct
9 Correct 214 ms 23036 KB Output is correct
10 Correct 200 ms 17012 KB Output is correct
11 Incorrect 196 ms 20080 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 32 ms 1696 KB Output is correct
20 Correct 29 ms 1744 KB Output is correct
21 Correct 46 ms 1868 KB Output is correct
22 Correct 25 ms 1924 KB Output is correct
23 Correct 26 ms 2124 KB Output is correct
24 Correct 23 ms 2132 KB Output is correct
25 Correct 29 ms 1816 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 174 ms 16012 KB Output is correct
20 Correct 175 ms 15952 KB Output is correct
21 Correct 181 ms 15972 KB Output is correct
22 Incorrect 179 ms 18756 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 16600 KB Output is correct
2 Correct 189 ms 16676 KB Output is correct
3 Correct 213 ms 16548 KB Output is correct
4 Correct 211 ms 22976 KB Output is correct
5 Correct 213 ms 16980 KB Output is correct
6 Incorrect 268 ms 22788 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 340 KB Output is correct
2 Correct 186 ms 16612 KB Output is correct
3 Correct 196 ms 16608 KB Output is correct
4 Correct 250 ms 16656 KB Output is correct
5 Correct 201 ms 17304 KB Output is correct
6 Correct 213 ms 17772 KB Output is correct
7 Correct 208 ms 17820 KB Output is correct
8 Correct 215 ms 22948 KB Output is correct
9 Correct 214 ms 23036 KB Output is correct
10 Correct 200 ms 17012 KB Output is correct
11 Incorrect 196 ms 20080 KB Output isn't correct
12 Halted 0 ms 0 KB -