oj.uz

답안 #750515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750515 2023-05-29T15:20:15 Z vjudge1 Event Hopping (BOI22_events) C++17
100 / 100
 413 ms 46128 KB 
#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 4e5 + 5;
const int LOG = 20;
pair<int , int> seg[N << 2];
map<int , int> mp , mpp;
vector<pair<int , int> > vp;
vector<int> vec;
int dp[N][LOG] , s[N] , e[N] , num , n , q;

void compress(){
	// sort(vec.begin() , vec.end());
	// mp[vec[0]] = num;
	// for(int i = 1 ; i < (int)vec.size() ; i++){
	// 	if(vec[i] == vec[i - 1]) continue;
	// 	mp[vec[i]] = ++num;
	// }

	// for(int i = 1 ; i <= n ; i++){
	// 	s[i] = mp[s[i]];
	// 	e[i] = mp[e[i]];
	// }

	for(int i = 1 ; i <= n ; i++){
		mp[s[i]] = 1;
		mp[e[i]] = 1;
	}

	for(auto i : mp)
		mpp[i.first] = ++num;

	for(int i = 1 ; i <= n ; i++){
		s[i] = mpp[s[i]];
		e[i] = mpp[e[i]];
		// cout << "aga " << s[i] << ' ' << e[i] << '\n';
	}
}

void clr(){
	for(int i = 0 ; i < (N << 2) ; i++)
		seg[i] = {INF , INF};
}

void update(int ver , int left , int right , int ind , int st , int ed){
	if(ed < left || right <= ed)
		return;

	if(left + 1 == right){
		if(seg[ver].first > st)
			seg[ver] = {st , ind};
		return;
	}

	int mid = (right + left) >> 1;
	update(ver << 1 , left , mid , ind , st , ed);
	update(ver << 1 | 1 , mid , right , ind , st , ed);
	if(seg[ver << 1].first > seg[ver << 1 | 1].first)
		seg[ver] = seg[ver << 1 | 1];
	else
		seg[ver] = seg[ver << 1];
}

pair<int , int> get(int ver , int left , int right , int l , int r){
	if(left >= r || right <= l)
		return {INF , INF};
	if(left >= l && right <= r)
		return seg[ver];
	int mid = (right + left) >> 1;
	pair<int , int> ans1 = get(ver << 1 , left , mid , l , r);
	pair<int , int> ans2 = get(ver << 1 | 1 , mid , right , l , r);
	if(ans1.first > ans2.first)
		return ans2;
	else
		return ans1;
}

void cal(){
	for(int i = 1 ; i <= n ; i++)
		update(1 , 1 , N , i , s[i] , e[i]);

	for(int i = 1 ; i <= n ; i++){
		vp.push_back(get(1 , 1 , N , s[i] , e[i] + 1));
		// cout << i << ": "  << vp.back().first << ' ' << vp.back().second << '\n';
	}
}

void find_dp(){
	for(int i = 1 ; i <= n ; i++)
		dp[i][0] = (vp[i - 1].first >= s[i] ? -1 : vp[i - 1].second);
	for(int j = 1 ; j < LOG ; j++)
		for(int i = 1 ; i <= n ; i++)
			dp[i][j] = (dp[i][j - 1] == -1 ? -1 : dp[dp[i][j - 1]][j - 1]);
}

int result(int fir , int las){
	int res = 0;
	for(int i = LOG - 1 ; i >= 0 ; i--){
		int idx = dp[las][i];
		if(idx == -1)
			continue;
		//if(s[dp[dp[las][i]][i]] > s[idx])
		//idx = -1;
		//break;
		if(s[idx] <= e[fir])
			continue;

		las = idx;
		res |= (1 << i);
	}
	// cout << "ajab " << las << '\n'; 
	if(dp[las][0] == -1)
		return -1;
	else
		return res;
}

void output(){
	while(q--){
		int fir , las;
		cin >> fir >> las;
		if(fir == las){
			cout << 0 << '\n';
			continue;
		}

		if(e[fir] > e[las]){
			cout << "impossible" << '\n';
			continue;
		}
		else if(e[fir] <= e[las] && e[fir] >= s[las]){
			cout << 1 << '\n';
			continue;
		}

		int ans = result(fir , las);
		if(ans == -1) cout << "impossible" << '\n';
		else cout << ans + 2 << '\n';
	}
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	clr();

	cin >> n >> q;
	for(int i = 1 ; i <= n ; i++){
		cin >> s[i] >> e[i];
		vec.push_back(s[i]);
		vec.push_back(e[i]);
	}

	compress();

	cal();

	find_dp();

	// for(int i = 1 ; i <= n ; i++)
	// 	cout << dp[i][0] << '\n';

	output();
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 380 ms 33216 KB Output is correct
3 Correct 247 ms 33292 KB Output is correct
4 Correct 273 ms 33172 KB Output is correct
5 Correct 216 ms 34240 KB Output is correct
6 Correct 214 ms 35112 KB Output is correct
7 Correct 279 ms 35364 KB Output is correct
8 Correct 319 ms 43060 KB Output is correct
9 Correct 304 ms 43072 KB Output is correct
10 Correct 298 ms 33536 KB Output is correct
11 Correct 333 ms 37424 KB Output is correct
12 Correct 165 ms 33772 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12848 KB Output is correct
2 Correct 11 ms 12756 KB Output is correct
3 Correct 8 ms 13024 KB Output is correct
4 Correct 11 ms 13012 KB Output is correct
5 Correct 11 ms 13012 KB Output is correct
6 Correct 11 ms 12992 KB Output is correct
7 Correct 11 ms 13124 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Correct 7 ms 12992 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12848 KB Output is correct
2 Correct 11 ms 12756 KB Output is correct
3 Correct 8 ms 13024 KB Output is correct
4 Correct 11 ms 13012 KB Output is correct
5 Correct 11 ms 13012 KB Output is correct
6 Correct 11 ms 12992 KB Output is correct
7 Correct 11 ms 13124 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Correct 7 ms 12992 KB Output is correct
10 Correct 8 ms 12756 KB Output is correct
11 Correct 8 ms 12756 KB Output is correct
12 Correct 10 ms 12988 KB Output is correct
13 Correct 8 ms 13000 KB Output is correct
14 Correct 9 ms 12988 KB Output is correct
15 Correct 9 ms 13012 KB Output is correct
16 Correct 9 ms 13120 KB Output is correct
17 Correct 8 ms 13120 KB Output is correct
18 Correct 10 ms 12884 KB Output is correct
19 Correct 63 ms 14788 KB Output is correct
20 Correct 41 ms 14564 KB Output is correct
21 Correct 53 ms 14824 KB Output is correct
22 Correct 41 ms 14892 KB Output is correct
23 Correct 51 ms 15200 KB Output is correct
24 Correct 50 ms 15224 KB Output is correct
25 Correct 51 ms 14888 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12848 KB Output is correct
2 Correct 11 ms 12756 KB Output is correct
3 Correct 8 ms 13024 KB Output is correct
4 Correct 11 ms 13012 KB Output is correct
5 Correct 11 ms 13012 KB Output is correct
6 Correct 11 ms 12992 KB Output is correct
7 Correct 11 ms 13124 KB Output is correct
8 Correct 8 ms 13140 KB Output is correct
9 Correct 7 ms 12992 KB Output is correct
10 Correct 7 ms 12756 KB Output is correct
11 Correct 10 ms 12756 KB Output is correct
12 Correct 9 ms 13012 KB Output is correct
13 Correct 9 ms 13012 KB Output is correct
14 Correct 8 ms 13012 KB Output is correct
15 Correct 8 ms 13012 KB Output is correct
16 Correct 10 ms 13140 KB Output is correct
17 Correct 9 ms 13144 KB Output is correct
18 Correct 9 ms 12960 KB Output is correct
19 Correct 247 ms 32812 KB Output is correct
20 Correct 233 ms 32820 KB Output is correct
21 Correct 393 ms 32784 KB Output is correct
22 Correct 288 ms 36272 KB Output is correct
23 Correct 413 ms 43844 KB Output is correct
24 Correct 408 ms 43768 KB Output is correct
25 Correct 63 ms 24408 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 33180 KB Output is correct
2 Correct 249 ms 33232 KB Output is correct
3 Correct 316 ms 33224 KB Output is correct
4 Correct 278 ms 43176 KB Output is correct
5 Correct 322 ms 33592 KB Output is correct
6 Correct 372 ms 42748 KB Output is correct
7 Correct 400 ms 45748 KB Output is correct
8 Correct 375 ms 45832 KB Output is correct
9 Correct 383 ms 43848 KB Output is correct
10 Correct 341 ms 45368 KB Output is correct
11 Correct 365 ms 45120 KB Output is correct
12 Correct 368 ms 45396 KB Output is correct

Subtask #6
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 380 ms 33216 KB Output is correct
3 Correct 247 ms 33292 KB Output is correct
4 Correct 273 ms 33172 KB Output is correct
5 Correct 216 ms 34240 KB Output is correct
6 Correct 214 ms 35112 KB Output is correct
7 Correct 279 ms 35364 KB Output is correct
8 Correct 319 ms 43060 KB Output is correct
9 Correct 304 ms 43072 KB Output is correct
10 Correct 298 ms 33536 KB Output is correct
11 Correct 333 ms 37424 KB Output is correct
12 Correct 165 ms 33772 KB Output is correct
13 Correct 6 ms 12848 KB Output is correct
14 Correct 11 ms 12756 KB Output is correct
15 Correct 8 ms 13024 KB Output is correct
16 Correct 11 ms 13012 KB Output is correct
17 Correct 11 ms 13012 KB Output is correct
18 Correct 11 ms 12992 KB Output is correct
19 Correct 11 ms 13124 KB Output is correct
20 Correct 8 ms 13140 KB Output is correct
21 Correct 7 ms 12992 KB Output is correct
22 Correct 8 ms 12756 KB Output is correct
23 Correct 8 ms 12756 KB Output is correct
24 Correct 10 ms 12988 KB Output is correct
25 Correct 8 ms 13000 KB Output is correct
26 Correct 9 ms 12988 KB Output is correct
27 Correct 9 ms 13012 KB Output is correct
28 Correct 9 ms 13120 KB Output is correct
29 Correct 8 ms 13120 KB Output is correct
30 Correct 10 ms 12884 KB Output is correct
31 Correct 63 ms 14788 KB Output is correct
32 Correct 41 ms 14564 KB Output is correct
33 Correct 53 ms 14824 KB Output is correct
34 Correct 41 ms 14892 KB Output is correct
35 Correct 51 ms 15200 KB Output is correct
36 Correct 50 ms 15224 KB Output is correct
37 Correct 51 ms 14888 KB Output is correct
38 Correct 7 ms 12756 KB Output is correct
39 Correct 10 ms 12756 KB Output is correct
40 Correct 9 ms 13012 KB Output is correct
41 Correct 9 ms 13012 KB Output is correct
42 Correct 8 ms 13012 KB Output is correct
43 Correct 8 ms 13012 KB Output is correct
44 Correct 10 ms 13140 KB Output is correct
45 Correct 9 ms 13144 KB Output is correct
46 Correct 9 ms 12960 KB Output is correct
47 Correct 247 ms 32812 KB Output is correct
48 Correct 233 ms 32820 KB Output is correct
49 Correct 393 ms 32784 KB Output is correct
50 Correct 288 ms 36272 KB Output is correct
51 Correct 413 ms 43844 KB Output is correct
52 Correct 408 ms 43768 KB Output is correct
53 Correct 63 ms 24408 KB Output is correct
54 Correct 273 ms 33180 KB Output is correct
55 Correct 249 ms 33232 KB Output is correct
56 Correct 316 ms 33224 KB Output is correct
57 Correct 278 ms 43176 KB Output is correct
58 Correct 322 ms 33592 KB Output is correct
59 Correct 372 ms 42748 KB Output is correct
60 Correct 400 ms 45748 KB Output is correct
61 Correct 375 ms 45832 KB Output is correct
62 Correct 383 ms 43848 KB Output is correct
63 Correct 341 ms 45368 KB Output is correct
64 Correct 365 ms 45120 KB Output is correct
65 Correct 368 ms 45396 KB Output is correct
66 Correct 7 ms 12756 KB Output is correct
67 Correct 257 ms 36204 KB Output is correct
68 Correct 294 ms 36236 KB Output is correct
69 Correct 342 ms 36168 KB Output is correct
70 Correct 279 ms 37232 KB Output is correct
71 Correct 298 ms 38132 KB Output is correct
72 Correct 265 ms 38340 KB Output is correct
73 Correct 316 ms 46128 KB Output is correct
74 Correct 287 ms 46112 KB Output is correct
75 Correct 291 ms 36576 KB Output is correct
76 Correct 279 ms 40420 KB Output is correct
77 Correct 170 ms 35956 KB Output is correct
78 Correct 7 ms 12756 KB Output is correct
79 Correct 8 ms 13012 KB Output is correct
80 Correct 8 ms 13012 KB Output is correct
81 Correct 11 ms 12984 KB Output is correct
82 Correct 9 ms 13012 KB Output is correct
83 Correct 11 ms 13124 KB Output is correct
84 Correct 9 ms 13140 KB Output is correct
85 Correct 7 ms 12884 KB Output is correct
86 Correct 41 ms 15448 KB Output is correct
87 Correct 43 ms 15404 KB Output is correct
88 Correct 59 ms 15540 KB Output is correct
89 Correct 40 ms 15732 KB Output is correct
90 Correct 40 ms 16012 KB Output is correct
91 Correct 38 ms 15948 KB Output is correct
92 Correct 40 ms 15632 KB Output is correct
93 Correct 195 ms 34408 KB Output is correct
94 Correct 223 ms 33652 KB Output is correct
95 Correct 242 ms 34348 KB Output is correct
96 Correct 263 ms 37912 KB Output is correct
97 Correct 343 ms 43864 KB Output is correct
98 Correct 320 ms 43852 KB Output is correct
99 Correct 61 ms 24408 KB Output is correct
100 Correct 409 ms 45736 KB Output is correct
101 Correct 355 ms 45772 KB Output is correct
102 Correct 328 ms 45908 KB Output is correct
103 Correct 373 ms 45352 KB Output is correct
104 Correct 347 ms 45120 KB Output is correct
105 Correct 345 ms 45400 KB Output is correct
106 Correct 208 ms 33256 KB Output is correct
107 Correct 256 ms 35672 KB Output is correct
108 Correct 241 ms 36320 KB Output is correct
109 Correct 229 ms 36296 KB Output is correct
110 Correct 378 ms 45616 KB Output is correct
111 Correct 379 ms 45724 KB Output is correct