oj.uz

Submission #791931

# Submission time Handle Problem Language Result Execution time Memory
791931 2023-07-24T12:39:22 Z ToniB Event Hopping (BOI22_events) C++17
20 / 100
 364 ms 37084 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 2;
const int LOG = 17;

int n, q, s[MAXN], e[MAXN], bl[MAXN][LOG];
set<pair<int, int> > st;
vector<pair<int, bool> > v[MAXN];

int main(){
	cin >> n >> q;
	unordered_map<int, int> um;
	vector<int> cmp;
	for(int i = 0; i < n; ++i){
		cin >> s[i] >> e[i];
		cmp.push_back(s[i]);
		cmp.push_back(e[i]);
	}
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	for(int i = 0; i < (int)cmp.size(); ++i){
		um[cmp[i]] = i;
	}
	for(int i = 0; i < n; ++i){
		s[i] = um[s[i]]; e[i] = um[e[i]];
		v[s[i]].push_back({i, 0});
		v[e[i]].push_back({i, 1});
	}
	for(int i = 0; i < 2*n; ++i){
		for(pair<int, bool> p : v[i]){
			if(!p.second){
				st.insert({e[p.first], p.first});
			}
		}
		for(pair<int, bool> p : v[i]){
			if(p.second){
				int idx = (*--st.end()).second;
				assert(s[idx] <= e[p.first] && e[p.first] <= e[idx]);
				bl[p.first][0] = idx;
//				cout << p.first << " -> " << idx << "\n";
			}
		}
	}
	for(int j = 1; j < LOG; ++j){
		for(int i = 0; i < n; ++i){
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}
	while(q--){
		int qs, qe; cin >> qs >> qe, --qs, --qe;
		if(qs == qe){
			cout << "0\n"; continue;
		} else if(s[qs] <= s[qe] && s[qe] <= e[qs]){
			cout << "1\n"; continue;
		} else if(e[qs] > e[qe]){
			cout << "impossible\n"; continue;
		}

		int ret = 0;
		for(int i = LOG - 1; i >= 0; --i){
			int idx = bl[qs][i];
			if(e[idx] < s[qe]){
				qs = idx;
				ret += 1 << i;
			}
		}
		if(e[bl[qs][0]] < s[qe]) cout << "impossible\n";
		else cout << ret + 2 << "\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 2 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 26132 KB Output is correct
2 Correct 277 ms 26040 KB Output is correct
3 Correct 337 ms 26108 KB Output is correct
4 Correct 304 ms 34204 KB Output is correct
5 Correct 298 ms 26428 KB Output is correct
6 Correct 364 ms 33932 KB Output is correct
7 Correct 363 ms 36956 KB Output is correct
8 Correct 344 ms 37084 KB Output is correct
9 Correct 197 ms 35120 KB Output is correct
10 Correct 339 ms 36676 KB Output is correct
11 Correct 364 ms 36364 KB Output is correct
12 Correct 355 ms 36664 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -