oj.uz

Submission #1066968

# Submission time Handle Problem Language Result Execution time Memory
1066968 2024-08-20T09:07:43 Z 0npata Fire (BOI24_fire) C++17
13 / 100
 221 ms 94996 KB 
#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);
		}
	}
	if(ans == INF) cout << -1 << '\n';
	else 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct
16 Correct 4 ms 2396 KB Output is correct
17 Correct 5 ms 2768 KB Output is correct
18 Correct 4 ms 2396 KB Output is correct
19 Correct 4 ms 2396 KB Output is correct
20 Correct 139 ms 93476 KB Output is correct
21 Correct 180 ms 83996 KB Output is correct
22 Correct 180 ms 84012 KB Output is correct
23 Correct 142 ms 82968 KB Output is correct
24 Correct 184 ms 83988 KB Output is correct
25 Correct 221 ms 94996 KB Output is correct
26 Correct 155 ms 83992 KB Output is correct
27 Correct 151 ms 83996 KB Output is correct
28 Correct 159 ms 83992 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 2412 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 6 ms 2392 KB Output is correct
15 Correct 137 ms 93352 KB Output is correct
16 Correct 134 ms 82984 KB Output is correct
17 Incorrect 162 ms 83992 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -