Submission #593960

#	Time	Username	Problem	Language	Result	Execution time	Memory
593960		CaroLinda	Event Hopping (BOI22_events)	C++14	40 / 100	1584 ms	3056 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(){
	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;
	}
}

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;

		int ans = 0;

		while(b != -1 && !isInside(a,b)){
			b = dp[0][b];
			ans++;
		}

		ans += (a != b);

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

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