oj.uz

Submission #828980

# Submission time Handle Problem Language Result Execution time Memory
828980 2023-08-17T22:24:13 Z QwertyPi Event Hopping (BOI22_events) C++14
55 / 100
 363 ms 65584 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 l2[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;

struct query{
	int u, v, t;
};

int ans[N];

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++) p[a[i].i] = i;

	vector<query> Q;
	for(int i = 0; i < q; i++){
		int u, v; cin >> u >> v; u = p[u], v = p[v];
		Q.push_back({u, v, i});
	}
	sort(Q.begin(), Q.end(), [](query a, query b){ return a.v < b.v; }); int qi = 0;
	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];
		while(qi < Q.size() && Q[qi].v == i){
			int u = Q[qi].u, v = Q[qi].v, t = Q[qi].t;
			if(a[u].e > a[v].e) ans[t] = -1;
			else if(u == v) ans[t] = 0;
			else if(a[v].s <= a[u].e && a[u].e <= a[v].e) ans[t] = 1;
			else {
				ans[t] = 2;
				int x = a[v].s;
				for(int j = 19; j >= 0; j--){
					if(a[u].e < lift[x][j]) ans[t] += (1 << j), x = lift[x][j];
				}
			}
			qi++;
		}
	}

	for(int i = 0; i < q; i++){
		cout << (ans[i] == -1 || ans[i] > N ? "impossible" : to_string(ans[i])) << '\n';
	}
}

Compilation message

events.cpp: In function 'int32_t main()':
events.cpp:70:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   while(qi < Q.size() && Q[qi].v == i){
      |         ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 242 ms 38432 KB Output is correct
3 Correct 229 ms 38384 KB Output is correct
4 Correct 240 ms 38456 KB Output is correct
5 Correct 238 ms 41076 KB Output is correct
6 Correct 271 ms 43620 KB Output is correct
7 Correct 238 ms 44392 KB Output is correct
8 Correct 281 ms 65572 KB Output is correct
9 Correct 344 ms 65584 KB Output is correct
10 Correct 248 ms 38836 KB Output is correct
11 Correct 274 ms 49348 KB Output is correct
12 Correct 179 ms 38892 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6652 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6868 KB Output is correct
4 Correct 4 ms 6868 KB Output is correct
5 Correct 3 ms 6868 KB Output is correct
6 Correct 4 ms 6868 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct
8 Correct 4 ms 6996 KB Output is correct
9 Correct 3 ms 6612 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6652 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6868 KB Output is correct
4 Correct 4 ms 6868 KB Output is correct
5 Correct 3 ms 6868 KB Output is correct
6 Correct 4 ms 6868 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct
8 Correct 4 ms 6996 KB Output is correct
9 Correct 3 ms 6612 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6484 KB Output is correct
12 Correct 4 ms 6868 KB Output is correct
13 Correct 4 ms 6868 KB Output is correct
14 Correct 4 ms 6844 KB Output is correct
15 Correct 5 ms 6868 KB Output is correct
16 Correct 4 ms 7124 KB Output is correct
17 Correct 4 ms 6996 KB Output is correct
18 Correct 3 ms 6612 KB Output is correct
19 Correct 59 ms 12644 KB Output is correct
20 Correct 64 ms 12700 KB Output is correct
21 Correct 67 ms 13000 KB Output is correct
22 Incorrect 59 ms 13132 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6652 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6868 KB Output is correct
4 Correct 4 ms 6868 KB Output is correct
5 Correct 3 ms 6868 KB Output is correct
6 Correct 4 ms 6868 KB Output is correct
7 Correct 4 ms 7124 KB Output is correct
8 Correct 4 ms 6996 KB Output is correct
9 Correct 3 ms 6612 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 2 ms 6484 KB Output is correct
12 Correct 4 ms 6868 KB Output is correct
13 Correct 4 ms 6868 KB Output is correct
14 Correct 4 ms 6844 KB Output is correct
15 Correct 4 ms 6848 KB Output is correct
16 Correct 4 ms 7124 KB Output is correct
17 Correct 4 ms 7008 KB Output is correct
18 Correct 3 ms 6584 KB Output is correct
19 Correct 175 ms 37272 KB Output is correct
20 Correct 158 ms 38240 KB Output is correct
21 Correct 181 ms 38964 KB Output is correct
22 Correct 204 ms 48760 KB Output is correct
23 Correct 251 ms 49984 KB Output is correct
24 Correct 251 ms 65496 KB Output is correct
25 Correct 63 ms 11748 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 38472 KB Output is correct
2 Correct 235 ms 38436 KB Output is correct
3 Correct 241 ms 38516 KB Output is correct
4 Correct 274 ms 65484 KB Output is correct
5 Correct 236 ms 38848 KB Output is correct
6 Correct 363 ms 65164 KB Output is correct
7 Correct 314 ms 65132 KB Output is correct
8 Correct 313 ms 65292 KB Output is correct
9 Correct 248 ms 48012 KB Output is correct
10 Correct 336 ms 64820 KB Output is correct
11 Correct 338 ms 60756 KB Output is correct
12 Correct 301 ms 64860 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 242 ms 38432 KB Output is correct
3 Correct 229 ms 38384 KB Output is correct
4 Correct 240 ms 38456 KB Output is correct
5 Correct 238 ms 41076 KB Output is correct
6 Correct 271 ms 43620 KB Output is correct
7 Correct 238 ms 44392 KB Output is correct
8 Correct 281 ms 65572 KB Output is correct
9 Correct 344 ms 65584 KB Output is correct
10 Correct 248 ms 38836 KB Output is correct
11 Correct 274 ms 49348 KB Output is correct
12 Correct 179 ms 38892 KB Output is correct
13 Correct 3 ms 6652 KB Output is correct
14 Correct 3 ms 6484 KB Output is correct
15 Correct 4 ms 6868 KB Output is correct
16 Correct 4 ms 6868 KB Output is correct
17 Correct 3 ms 6868 KB Output is correct
18 Correct 4 ms 6868 KB Output is correct
19 Correct 4 ms 7124 KB Output is correct
20 Correct 4 ms 6996 KB Output is correct
21 Correct 3 ms 6612 KB Output is correct
22 Correct 3 ms 6484 KB Output is correct
23 Correct 3 ms 6484 KB Output is correct
24 Correct 4 ms 6868 KB Output is correct
25 Correct 4 ms 6868 KB Output is correct
26 Correct 4 ms 6844 KB Output is correct
27 Correct 5 ms 6868 KB Output is correct
28 Correct 4 ms 7124 KB Output is correct
29 Correct 4 ms 6996 KB Output is correct
30 Correct 3 ms 6612 KB Output is correct
31 Correct 59 ms 12644 KB Output is correct
32 Correct 64 ms 12700 KB Output is correct
33 Correct 67 ms 13000 KB Output is correct
34 Incorrect 59 ms 13132 KB Output isn't correct
35 Halted 0 ms 0 KB -