oj.uz

Submission #828978

# Submission time Handle Problem Language Result Execution time Memory
828978 2023-08-17T22:00:43 Z QwertyPi Event Hopping (BOI22_events) C++14
30 / 100
 467 ms 67872 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 2e5 + 11;
struct event{
	int s, e, i;
};

event a[N];
int p[N], R[N];
int lift[N][20];
int n, q; 

struct SegTree{
	int t[N << 2];
	void update(int p, int val, int v = 0, int l = 0, int r = n * 2){
		if(l == r) t[v] = min(t[v], val);
		else {
			int m = (l + r) / 2;
			if(p <= m) update(p, val, v * 2 + 1, l, m);
			else update(p, val, v * 2 + 2, m + 1, r);
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	int query_suff_min(int p, int v = 0, int l = 0, int r = n * 2){
		if(l == r) return t[v];
		int m = (l + r) / 2;
		if(p <= m) return min(query_suff_min(p, v * 2 + 1, l, m), t[v * 2 + 2]);
		else return query_suff_min(p, v * 2 + 2, m + 1, r);
	}
} ST;
int32_t main(){
	fill(ST.t, ST.t + (N << 2), 1 << 30);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		int s, e; cin >> s >> e; a[i] = {s, e, i};
	}
	{
		set<int> S; map<int, int> mp;
		for(int i = 1; i <= n; i++) S.insert(a[i].s), S.insert(a[i].e);
		int id = 1; for(auto i : S) mp[i] = id++;
		for(int i = 1; i <= n; i++) a[i].s = mp[a[i].s], a[i].e = mp[a[i].e];
	}
	sort(a + 1, a + n + 1, [](event u, event v){ return u.e < v.e; });
	R[n] = n; for(int i = n - 1; i >= 1; i--) R[i] = a[i].e == a[i + 1].e ? R[i + 1] : i;

	for(int i = 1; i <= n; i++){
		for(int j = R[i - 1] + 1; j <= R[i]; j++) ST.update(a[j].e, a[j].s);
		lift[a[i].s][0] = ST.query_suff_min(a[i].s);
		for(int j = 1; j < 20; j++) lift[a[i].s][j] = lift[lift[a[i].s][j - 1]][j - 1];
	}
	for(int i = 1; i <= n; i++) p[a[i].i] = i;
	for(int i = 0; i < q; i++){
		int u, v; cin >> u >> v; u = p[u], v = p[v];
		if(a[u].e > a[v].e){
			cout << "impossible" << endl;
			continue;
		}
		if(u == v){
			cout << 0 << endl;
			continue;
		}
		if(a[v].s <= a[u].e && a[u].e <= a[v].e){
			cout << 1 << endl;
			continue;
		}
		int ans = 0, x = a[v].s;
		for(int j = 19; j >= 0; j--){
			if(a[u].e < lift[x][j]) ans += (1 << j), x = lift[x][j];
		}
		cout << (ans >= (1 << 19) ? "impossible" : to_string(ans + 2)) << endl;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 370 ms 38944 KB Output is correct
3 Correct 318 ms 40700 KB Output is correct
4 Correct 344 ms 40740 KB Output is correct
5 Correct 342 ms 43412 KB Output is correct
6 Correct 344 ms 45952 KB Output is correct
7 Correct 347 ms 46724 KB Output is correct
8 Correct 377 ms 67872 KB Output is correct
9 Correct 382 ms 67856 KB Output is correct
10 Correct 380 ms 41164 KB Output is correct
11 Correct 355 ms 51720 KB Output is correct
12 Correct 274 ms 40488 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 2 ms 6484 KB Output is correct
3 Correct 6 ms 6868 KB Output is correct
4 Correct 5 ms 6868 KB Output is correct
5 Correct 4 ms 6828 KB Output is correct
6 Incorrect 4 ms 6864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 2 ms 6484 KB Output is correct
3 Correct 6 ms 6868 KB Output is correct
4 Correct 5 ms 6868 KB Output is correct
5 Correct 4 ms 6828 KB Output is correct
6 Incorrect 4 ms 6864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 2 ms 6484 KB Output is correct
3 Correct 6 ms 6868 KB Output is correct
4 Correct 5 ms 6868 KB Output is correct
5 Correct 4 ms 6828 KB Output is correct
6 Incorrect 4 ms 6864 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 38964 KB Output is correct
2 Correct 318 ms 40712 KB Output is correct
3 Correct 328 ms 40724 KB Output is correct
4 Correct 371 ms 67784 KB Output is correct
5 Correct 401 ms 41076 KB Output is correct
6 Correct 417 ms 67496 KB Output is correct
7 Correct 440 ms 67588 KB Output is correct
8 Correct 432 ms 67604 KB Output is correct
9 Correct 247 ms 50000 KB Output is correct
10 Correct 407 ms 67048 KB Output is correct
11 Correct 467 ms 63024 KB Output is correct
12 Correct 397 ms 67148 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 370 ms 38944 KB Output is correct
3 Correct 318 ms 40700 KB Output is correct
4 Correct 344 ms 40740 KB Output is correct
5 Correct 342 ms 43412 KB Output is correct
6 Correct 344 ms 45952 KB Output is correct
7 Correct 347 ms 46724 KB Output is correct
8 Correct 377 ms 67872 KB Output is correct
9 Correct 382 ms 67856 KB Output is correct
10 Correct 380 ms 41164 KB Output is correct
11 Correct 355 ms 51720 KB Output is correct
12 Correct 274 ms 40488 KB Output is correct
13 Correct 3 ms 6484 KB Output is correct
14 Correct 2 ms 6484 KB Output is correct
15 Correct 6 ms 6868 KB Output is correct
16 Correct 5 ms 6868 KB Output is correct
17 Correct 4 ms 6828 KB Output is correct
18 Incorrect 4 ms 6864 KB Output isn't correct
19 Halted 0 ms 0 KB -