oj.uz

Submission #750512

# Submission time Handle Problem Language Result Execution time Memory
750512 2023-05-29T15:18:45 Z vjudge1 Event Hopping (BOI22_events) C++17
25 / 100
 354 ms 33612 KB 
#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 1e5 + 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3440 KB Output is correct
2 Correct 327 ms 23772 KB Output is correct
3 Correct 230 ms 23676 KB Output is correct
4 Correct 254 ms 23712 KB Output is correct
5 Incorrect 209 ms 25148 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3640 KB Output is correct
4 Correct 3 ms 3668 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 3 ms 3668 KB Output is correct
7 Correct 4 ms 3668 KB Output is correct
8 Correct 4 ms 3760 KB Output is correct
9 Correct 3 ms 3528 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3640 KB Output is correct
4 Correct 3 ms 3668 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 3 ms 3668 KB Output is correct
7 Correct 4 ms 3668 KB Output is correct
8 Correct 4 ms 3760 KB Output is correct
9 Correct 3 ms 3528 KB Output is correct
10 Correct 3 ms 3464 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 ms 3668 KB Output is correct
13 Correct 3 ms 3668 KB Output is correct
14 Correct 3 ms 3596 KB Output is correct
15 Correct 4 ms 3592 KB Output is correct
16 Correct 5 ms 3796 KB Output is correct
17 Correct 4 ms 3796 KB Output is correct
18 Correct 2 ms 3540 KB Output is correct
19 Correct 47 ms 6128 KB Output is correct
20 Correct 35 ms 5912 KB Output is correct
21 Correct 36 ms 6236 KB Output is correct
22 Correct 39 ms 6244 KB Output is correct
23 Correct 41 ms 6572 KB Output is correct
24 Correct 35 ms 6608 KB Output is correct
25 Correct 37 ms 6284 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3640 KB Output is correct
4 Correct 3 ms 3668 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 3 ms 3668 KB Output is correct
7 Correct 4 ms 3668 KB Output is correct
8 Correct 4 ms 3760 KB Output is correct
9 Correct 3 ms 3528 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 3 ms 3668 KB Output is correct
13 Correct 4 ms 3668 KB Output is correct
14 Correct 4 ms 3592 KB Output is correct
15 Correct 4 ms 3600 KB Output is correct
16 Correct 4 ms 3796 KB Output is correct
17 Correct 4 ms 3728 KB Output is correct
18 Correct 3 ms 3540 KB Output is correct
19 Correct 174 ms 25052 KB Output is correct
20 Correct 243 ms 24300 KB Output is correct
21 Correct 202 ms 24936 KB Output is correct
22 Incorrect 202 ms 28492 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 23672 KB Output is correct
2 Correct 204 ms 23756 KB Output is correct
3 Correct 222 ms 23632 KB Output is correct
4 Correct 252 ms 33612 KB Output is correct
5 Correct 243 ms 24056 KB Output is correct
6 Incorrect 354 ms 33540 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3440 KB Output is correct
2 Correct 327 ms 23772 KB Output is correct
3 Correct 230 ms 23676 KB Output is correct
4 Correct 254 ms 23712 KB Output is correct
5 Incorrect 209 ms 25148 KB Output isn't correct
6 Halted 0 ms 0 KB -