Submission #1111441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111441		siewjh	Fire (BOI24_fire)	C++17	100 / 100	88 ms	19932 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int p[MAXN][20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	memset(p, -1, sizeof(p));
	int nums, len; cin >> nums >> len;
	vector<pair<int, int>> pv(nums);
	for (int i = 0; i < nums; i++){
		int a, b; cin >> a >> b;
		if (a > b) b += len;
		pv[i] = {a, b};
	}
	sort(pv.begin(), pv.end());
	for (int i = 0, pid = 0, fid, far = 0; i < nums; i++){
		int a, b; tie(a, b) = pv[i];
		for(; pid != nums && pv[pid].first <= b; pid++){
			int nb = pv[pid].second;
			if (nb > far){
				far = nb; fid = pid;
			}
		}
		if (far > b) p[i][0] = fid;
	}
	for (int k = 1; k <= 19; k++)
		for (int i = 0; i < nums; i++){
			if (p[i][k - 1] == -1) p[i][k] = -1;
			else p[i][k] = p[p[i][k - 1]][k - 1];
		}
	int ans = MAXN;
	for (int i = 0; i < nums; i++){
		int a, b, curr = i, res = 2; tie(a, b) = pv[i];
		for (int k = 19; k >= 0; k--){
			int nxt = p[curr][k];
			if (nxt != -1 && pv[nxt].second < a + len){
				curr = nxt; res += (1 << k);
			}
		}
		curr = p[curr][0];
		if (curr != -1 && pv[curr].second >= a + len) ans = min(ans, res);
	}
	cout << (ans == MAXN ? -1 : ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:24: warning: 'fid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |   if (far > b) p[i][0] = fid;
      |                ~~~~~~~~^~~~~

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