Submission #727348

#	Time	Username	Problem	Language	Result	Execution time	Memory
727348		Arturgo	Event Hopping (BOI22_events)	C++14	100 / 100	449 ms	59268 KiB

events

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

map<int, int> idxs;
vector<pair<int, int>> arbre((1 << 20), {INFINI, -1});

void set_min(int pos, pair<int, int> val) {
	pos += (1 << 19);
	
	while(pos != 0) {
		arbre[pos] = min(arbre[pos], val);
		pos /= 2;
	}
}

pair<int, int> get_min(int deb, int fin) {
	deb += (1 << 19);
	fin += (1 << 19);
	
	pair<int, int> mini = {INFINI, -1};
	while(deb < fin) {
		if(deb % 2 == 1) {
			mini = min(mini, arbre[deb]);
			deb++;
		}
		if(fin % 2 == 1) {
			fin--;
			mini = min(mini, arbre[fin]);
		}
		deb /= 2;
		fin /= 2;
	}
	
	return mini;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int N, Q;
	cin >> N >> Q;
	
	vector<pair<int, int>> inters;
	
	for(int i = 0;i < N;i++) {
		int deb, fin;
		cin >> deb >> fin;
		
		idxs[deb] = idxs[fin] = -1;
		
		inters.push_back({deb, fin});
	}
	
	int iIdx = 0;
	for(auto it = idxs.begin();it != idxs.end();it++) {
		it->second = iIdx++;
	}
	
	int iInter = 0;
	for(pair<int, int>& inter : inters) {
		inter.first = idxs[inter.first];
		inter.second = idxs[inter.second];
		set_min(inter.second, {inter.first, iInter});
		iInter++;
	}
	
	vector<vector<int>> parents(
		30, 
		vector<int>(inters.size(), -1)
	);
	
	for(int iInter = 0;iInter < (int)inters.size();iInter++) {
		parents[0][iInter] = get_min(inters[iInter].first, inters[iInter].second + 1).second;
	}
	
	for(int lvl = 1;lvl < 30;lvl++) {
		for(int iInter = 0;iInter < (int)inters.size();iInter++) {
			parents[lvl][iInter] = parents[lvl - 1][parents[lvl - 1][iInter]];
		}
	}
	
	for(int iReq = 0;iReq < Q;iReq++) {
		int deb, fin;
		cin >> deb >> fin;
		deb--; fin--;
		
		if(inters[deb].second > inters[fin].second) {
			cout << "impossible\n";
			continue;
		}
		
		if(deb == fin) {
			cout << "0\n";
			continue;
		}
		
		if(inters[deb].second <= inters[fin].second && inters[deb].second >= inters[fin].first) {
			cout << "1\n";
			continue;
		}
		
		int cur = fin;
		int nbSteps = 0;
		for(int iHop = 29;iHop >= 0;iHop--) {
			if(inters[parents[iHop][cur]].first > inters[deb].second) {
				nbSteps += (1 << iHop);
				cur = parents[iHop][cur];
			}
		}
		
		if(inters[parents[0][cur]].first <= inters[deb].second) {
			cout << nbSteps + 2 << "\n";
		}
		else {
			cout << "impossible\n";
		}
	}
	
	return 0;
}

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