oj.uz

Submission #750498

# Submission time Handle Problem Language Result Execution time Memory
750498 2023-05-29T15:01:02 Z vjudge1 Event Hopping (BOI22_events) C++17
0 / 100
 273 ms 23788 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] && s[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 3412 KB Output is correct
2 Correct 241 ms 23788 KB Output is correct
3 Correct 232 ms 23752 KB Output is correct
4 Incorrect 273 ms 23748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 4 ms 3668 KB Output is correct
4 Incorrect 3 ms 3668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 4 ms 3668 KB Output is correct
4 Incorrect 3 ms 3668 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 4 ms 3668 KB Output is correct
4 Incorrect 3 ms 3668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 23780 KB Output is correct
2 Correct 253 ms 23732 KB Output is correct
3 Incorrect 259 ms 23660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 241 ms 23788 KB Output is correct
3 Correct 232 ms 23752 KB Output is correct
4 Incorrect 273 ms 23748 KB Output isn't correct
5 Halted 0 ms 0 KB -