oj.uz

답안 #791927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791927 2023-07-24T12:37:45 Z ToniB Event Hopping (BOI22_events) C++17
0 / 100
 340 ms 37400 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 if(bl[qs][1] != qe) cout << "impossible\n";
		else cout << ret + 2 << "\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 283 ms 29252 KB Output is correct
3 Correct 311 ms 29200 KB Output is correct
4 Correct 307 ms 29404 KB Output is correct
5 Correct 289 ms 29932 KB Output is correct
6 Correct 318 ms 30476 KB Output is correct
7 Incorrect 288 ms 30720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 3 ms 5148 KB Output is correct
5 Incorrect 4 ms 5204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 3 ms 5148 KB Output is correct
5 Incorrect 4 ms 5204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 3 ms 5148 KB Output is correct
5 Incorrect 4 ms 5204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 26136 KB Output is correct
2 Correct 271 ms 29152 KB Output is correct
3 Correct 295 ms 29256 KB Output is correct
4 Correct 307 ms 37284 KB Output is correct
5 Correct 276 ms 29612 KB Output is correct
6 Incorrect 340 ms 37400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 283 ms 29252 KB Output is correct
3 Correct 311 ms 29200 KB Output is correct
4 Correct 307 ms 29404 KB Output is correct
5 Correct 289 ms 29932 KB Output is correct
6 Correct 318 ms 30476 KB Output is correct
7 Incorrect 288 ms 30720 KB Output isn't correct
8 Halted 0 ms 0 KB -