Submission #1111492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111492		YSH2020	Fire (BOI24_fire)	C++17	35 / 100	149 ms	6708 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int n, m; cin >> n >> m;
	vector<pair<int, int>> shifts;
	int max_dist = 0;
	int start_x = 0;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		if (x > y) y += m;
		if (y-x > max_dist) {max_dist = y-x;start_x = x;}
		shifts.push_back({x, y});
	}
	for (int i=0; i < n; i++) {
		shifts[i] = {(shifts[i].first-start_x+2*m)%m, (shifts[i].second-start_x+2*m)%m};
		if (shifts[i].first > shifts[i].second) shifts[i]={shifts[i].first, shifts[i].second+m};
	}
	sort(shifts.begin(), shifts.end());
	int time = 0;
	int furthest_time = 0;
	int c = 0;
	for (int i=0; i < n; i++) {
		if (shifts[i].first <= time) furthest_time = max(furthest_time, shifts[i].second);
		else {
			c++;
			time = furthest_time;
			if (time >= m) {cout << c; return 0;}
			if (shifts[i].first > time) {cout << -1; return 0;}
			furthest_time = shifts[i].second;
		}
	}
	c++;
	time = furthest_time;
	if (time >= m) {cout << c; return 0;}
	else cout << -1;
}

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