Submission #1235131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235131		farica	Fire (BOI24_fire)	C++20	100 / 100	245 ms	41244 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5; // twice the contraints (since we duplicate intervals in modifyIntervals())
const int MAXK = 21; // ~log(MAXN), for binary lifting

long long n, m;
long long s[MAXN], e[MAXN];
int nextBest[MAXN];   // precalculated next best interval
int lift[MAXN][MAXK]; // precalculated binary lifting. lift[i][k] is taking 2^k intervals, starting from i-th one

void readInput() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> e[i];
	}
}

void removeUnnecessaryIntervals() {
	// interval is unnecessary if it is covered fully by other intervals

	int cnt = 0;

	// sort the intervals
	vector<pair<long long, long long>> intervals;
	for (int i = 0; i < n; i++) 
		intervals.push_back({s[i], -e[i]}); // this will help sort by increasing s[i], 
						    // and then by decreasing e[i]

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

	long long furthestEnd = -1;

	for (auto interval : intervals) {
		long long start = interval.first;
		long long end = -interval.second;

		if (end <= furthestEnd) { 
			continue; // this interval is unnecessary
		}

		furthestEnd = end;
		s[cnt] = start;
		e[cnt] = end;
		cnt++;
	}

	n = cnt; // update interval count
}

void modifyIntervals() {
	// to make implementation a bit easier
	
	// deal with the cases of s > e
	for (int i = 0; i < n; i++) {
		if (s[i] > e[i]) e[i] += m;
	}

	// duplicate all intervals: (s, e) -> (s+m, e+m)
	for (int i = 0; i < n; i++) {
		s[i+n] = s[i] + m;
		e[i+n] = e[i] + m;
	}

	n *= 2; // since we duplicated

	removeUnnecessaryIntervals(); // remove covered fully by other intervals
}

void precalcNexts() {
	// sort intervals by their starts
	vector<pair<long long, int>> intervals; // vector of pairs {start, id}
	for (int i = 0; i < n; i++) 
		intervals.push_back({s[i], i});
	sort(intervals.begin(), intervals.end());

	// calculate nexts with two pointers technique
	int i = 0;

	for (auto interval : intervals) {
		int id = interval.second;
		
		while (i < n) {
			int intervalId = intervals[i].second;
			if (s[intervalId] > e[id])  // not overlapping
				break;
			i++;
		}

		nextBest[id] = intervals[i - 1].second;
	}
}

void precalcBinaryLifting() {
	for (int i = 0; i < n; i++) 
		lift[i][0] = nextBest[i];

	for (int k = 1; k < MAXK; k++) for (int i = 0; i < n; i++)
		lift[i][k] = lift[ lift[i][k-1] ][k-1];
}

int tryFrom(int startAdmin) {
	long long startTime = s[startAdmin];

	// do binary lifting (binary search) to find the furthest reachable admin
	// such that it would still not cover full circle
	
	int cntJumps = 0;
	int curAdmin = startAdmin;

	for (int i = MAXK-1; i >= 0; i--) {
		int jumpedToId = lift[curAdmin][i];
		if (e[jumpedToId] < (startTime + m)) { // does not cover full circle
			cntJumps += (1<<i); // 2^i
			curAdmin = jumpedToId;
		}
	}

	// we found the last before we get to full circle
	cntJumps++;
	curAdmin = lift[curAdmin][0];

	if (e[curAdmin] < (startTime + m)) {
		return -1; // impossible since we did not cover full circle
	}

	return cntJumps + 1;
}

int main() {
	readInput();
	modifyIntervals(); // see the explanation at the top
	precalcNexts(); 
	precalcBinaryLifting();

	int ans = -1;
	for (int i = 0; i < n; i++) {
		int curTaken = tryFrom(i);

		// update ans
		if (curTaken == -1) continue; 
		if (ans == -1 || curTaken < ans) ans = curTaken;
	}

	cout << ans << endl;


	return 0;
}

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