Submission #1067014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067014		0npata	Fire (BOI24_fire)	C++17	40 / 100	2098 ms	95000 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++) {
		cerr << rs[i].first << ' ' << rs[i].second << '\n';
	}

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

	int j = 0;
	for(int i = 0; i<N; i++) {
		while(rs[j].first <= rs[i].second) {
			rightmost.insert({rs[j].second, j});
			cerr << "J: " << j;
			 j++;
		}
		pair<int, int> r = *rightmost.rbegin();
		assert(r.first >= rs[i].second);
		binjmps[i][0] = {r.first-rs[i].second, r.second%N};
		cerr << binjmps[i][0].first << ", " << binjmps[i][0].second << ';';
		rightmost.erase({rs[i].second, i});
	}

	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 = binjmps[k][i-1].second;
			if(binjmps[j][i].first > M) {
				mxlog = i+1;
			}
		}
	}
	for(int i = 0; i<mxlog; i++) {
		cerr << binjmps[0][i].first  << ' ';
	}
	cerr << '\n';

	int 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: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26