Submission #1140115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140115		AbdullahIshfaq	Fire (BOI24_fire)	C++20	40 / 100	2 ms	1476 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int N = 10000;
const int lg = 14;
ll n, m, s[N], e[N];
int bst[N];
int sp[N][lg];
void solve(){
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		cin >> s[i] >> e[i];
	}
	for (int i = 0; i < n; i++) {
		if (s[i] > e[i]){
			e[i] += m;
		}
	}
	for (int i = 0; i < n; i++) {
		s[i+n] = s[i] + m;
		e[i+n] = e[i] + m;
	}
	n *= 2;
	int cnt = 0;
	vector<pair<ll, ll>> ranges;
	for (int i = 0; i < n; i++) 
		ranges.push_back({s[i], -e[i]});
	sort(ranges.begin(), ranges.end());
	ll last = -1;
	for (auto j : ranges) {
		ll start = j.first;
		ll end = -j.second;
		if (end <= last) { 
			continue;
		}
		last = end;
		s[cnt] = start;
		e[cnt] = end;
		cnt++;
	}
	n = cnt;
	ranges.clear();
	for (int i = 0; i < n; i++) 
		ranges.push_back({s[i], i});
	sort(ranges.begin(), ranges.end());
	int i = 0;
	for (auto j : ranges) {
		while (i < n) {
			if (s[ranges[i].second] > e[j.second]){
				break;
			}
			i++;
		}
		bst[j.second] = ranges[i - 1].second;
	}
	for (int i = 0; i < n; i++){
		sp[i][0] = bst[i];
	}
	for (int k = 1; k < lg; k++) 
		for (int i = 0; i < n; i++)
			sp[i][k] = sp[sp[i][k-1]][k-1];
	int ans = -1;
	for (int i = 0; i < n; i++) {
		ll st = s[i];
		int mn = 0;
		int rt = i;
		for (int i = lg-1; i >= 0; i--) {
			if (e[sp[rt][i]] < (st + m)) { 
				mn += (1<<i);
				rt = sp[rt][i];
			}
		}
		mn++;
		rt = sp[rt][0];

		if (e[rt] < (st + m)) {
			continue;
		}
		if (ans == -1 or mn + 1 < ans) ans = mn + 1;
	}
	cout << ans << endl;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i++){
		solve();
	}
}

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