Submission #1066963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066963		0npata	Fire (BOI24_fire)	C++17	0 / 100	1 ms	348 KiB

Main

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

#define int long long
#define vec vector

const int MXN = 200'005;
const int LOG = 20;
const int INF = 1e9;

int32_t main() {
	int N, M;
	cin >> N >> M;

	vec<pair<int, int>> rs(N);
	for(int i = 0; i<N; i++) {
		cin >> rs[i].first >> rs[i].second;
		if(rs[i].second < rs[i].first) rs[i].second += M;
	}

	sort(rs.begin(), rs.end());

	set<pair<int, int>> rightmost;
	vec<vec<pair<int, int>>> binjmps(N, vec<pair<int, int>>(LOG));

	for(int i = 0; i<N; i++) {
		rs.push_back({rs[i].first+M, rs[i].second+M});
	}

	int j = 0;
	vec<int> dp(N*2, INF);
	for(int i = 0; i<N; i++) {
		if(rs[i].first == 0) dp[i] = 1;
	}
	for(int i = 0; i<N; i++) {
		while(rs[j].first <= rs[i].second) {
			rightmost.insert({rs[j].second, j});
			 j++;
		}
		pair<int, int> r = *rightmost.rbegin();
		assert(r.first >= rs[i].second);
		dp[r.second] = min(dp[r.second], dp[i]+1);
		binjmps[i][0] = {r.first-rs[i].second, r.second%N};
		//cerr << r.second%N << ' ';
		rightmost.erase({rs[i].second, i});
	}

	int ans = INF;
	for(int i = 0; i<N*2; i++) {
		if(rs[i].second >= M) {
			ans = min(dp[i], ans);
		}
	}
	cout << ans << '\n';
	return 0;

	//cerr << '\n';

	int mxlog = LOG;
	for(int i = 1; i<LOG && i<mxlog; i++) {
		for(int j = 0; j<N; j++) {
			int k = binjmps[j][i-1].second;
			binjmps[j][i].first = binjmps[j][i-1].first+binjmps[k][i-1].first;
			binjmps[j][i].second = k;
			if(binjmps[j][i].first > M) {
				mxlog = i+1;
			}
		}
	}

	ans = INF;

	for(int i = 0; i<N; i++) {
		int d = rs[i].second-rs[i].first;
		int cur = i;
		int res = 0;
		for(int j = mxlog-1; j>=0; j--) {
			int nd = binjmps[cur][j].first + d;
			if(nd < M) {
				d = nd;
				cur = binjmps[cur][j].second;
				res += (1<<j);
			}
		}
		res += 1;
		d += binjmps[cur][0].first;
		if(d >= M) {
			ans = min(ans, res+1);
		}
	}

	if(ans == INF) cout << -1 << '\n';
	else {
		cout << ans << '\n';
	}
}

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