Submission #1003335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003335		esomer	Fire (BOI24_fire)	C++17	100 / 100	133 ms	44912 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;

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

	int N, M; cin >> N >> M;
	vector<vector<pair<int, int>>> binlift(LOG, vector<pair<int, int>>(N));
	vector<pair<int, int>> inv(N);
	vector<int> s(N), e(N);
	for(int i = 0; i < N; i++){
		cin >> s[i] >> e[i];
		if(s[i] > e[i]) e[i] += M;
		inv[i] = {s[i], i};
	}
	sort(inv.begin(), inv.end());
	set<pair<int, int>> ending;
	for(auto [l, i] : inv){
		while(!ending.empty() && (*ending.begin()).first < l){
			binlift[0][(*ending.begin()).second] = *ending.rbegin();
			ending.erase(ending.begin());
		}
		ending.insert({e[i], i});
	}
	while(!ending.empty()){
		binlift[0][(*ending.begin()).second] = *ending.rbegin();
		ending.erase(ending.begin());
	}
	for(int k = 1; k < LOG; k++){
		for(int i = 0; i < N; i++){
			binlift[k][i] = binlift[k-1][binlift[k-1][i].second];
		}
	}
	int ans = 1e9;
	for(int i = 0; i < N; i++){
		int curr = i;
		int currAns = 0;
		for(int k = LOG - 1; k >= 0; k--){
			if(binlift[k][curr].first >= M && binlift[k][curr].first - M >= s[i]){
				ans = min(ans, currAns + (1 << k));
			}else{
				currAns += (1 << k);
				curr = binlift[k][curr].second;
			}
		}
	}
	cout << (ans == 1e9 ? -1 : ans + 1) << "\n";
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26