Submission #593968

#	Time	Username	Problem	Language	Result	Execution time	Memory
593968		CaroLinda	Event Hopping (BOI22_events)	C++14	100 / 100	142 ms	10512 KiB

events

#include <bits/stdc++.h>

//bad complexity to test idea

#define ll long long

const int MAXN = 1e5+10;
const int LOG = 20;

using namespace std;

int N, Q;
int S[MAXN], E[MAXN];
int dp[LOG][MAXN];


void findNxtArray(){
	for(int i = 0; i < LOG; i++)
		for(int j = 1; j <= N; j++)
			dp[i][j] = -1;

	vector<int> sweep(N);
	iota(sweep.begin(),sweep.end(), 1);

	sort(sweep.begin(),sweep.end(), [&](int a, int b){
		if(E[a] != E[b])
			return E[a] < E[b];
		return S[a] < S[b];
	});

	vector< pair<int,int> > s;

	for(auto &i : sweep){
		bool coloca = true;

		while(!s.empty()){
			int last = s.back().second;

			if(S[last] >= S[i]){
				s.pop_back();
			}
			else{
				if(E[last] == E[i]){
					coloca = false;
				}
				break;
			}
		}

		if(coloca)
			s.push_back(make_pair(E[i], i));

		int val = lower_bound(s.begin(),s.end(), make_pair(S[i],-1))->second;
		dp[0][i] = (val == i) ? -1 : val;
	}

	for(int i = 1; i < LOG; i++)
		for(int j = 1; j <= N; j++)
			if(dp[i-1][j] != -1)
				dp[i][j] = dp[i-1][ dp[i-1][j] ];
}

bool isInside(int a, int b){
	return E[a] >= S[b] && E[a] <= E[b];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++)
		cin >> S[i] >> E[i];

	findNxtArray();

	for(int i = 1, a, b; i <= Q; i++){
		cin >> a >> b;

		if(isInside(a,b)){
			cout << (a != b) << "\n";
			continue;
		}
		if(E[a] > S[b]){
			cout << "impossible\n";
			continue;
		}

		int ans = 0;

		for(int i = LOG-1; i >= 0 && !isInside(a,b); i--){
			if(dp[i][b] == -1)
				continue;
			if(S[dp[i][b]] > E[a]){
				ans += (1<<i);
				b = dp[i][b];
			}
		}

		b = dp[0][b];
		ans++;

		ans += (a != b);

		if(b == -1 || !isInside(a,b) ){
			cout << "impossible\n";
		}
		else cout << ans << "\n";
	} 
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30