POI 2010 - Frog

Explanation

To calculate the $k$-th closest rock from a certain location, we maintain a sliding window of size $k+1$. Essentially, we sweep left to right, and keep on moving the window right until either:

1. The window cannot be moved right any further.
2. Moving the window to the right would increase the maximum distance from this current location.

Afterwards, we can proceed to binary lift to get our answer. However, directly calculating binary lifts the traditional way would take up too much memory. From here, there are two ways to proceed:

Implementation 1

Iterate over the power of two we are lifting on in increasing order. Similar to binary exponentiation, we calculate the $2^{i}$-th next location at every step, and check if we need to use this current lift.

Time Complexity: $\mathcal{O}(N\log M)$

Space Complexity: $\mathcal{O}(N)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	ll m;
	cin >> n >> k >> m;
	vector<ll> rocks(n);

Implementation 2

Observe that a functional graph is constructed through these jumps. After $n$ jumps, any node that we start from will end up being inside a cycle. Thus, we can calculate our binary lifts like normal, and calculate the number of jumps, modulo the cycle size.

Time Complexity: $\mathcal{O}(N\log N)$

Space Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	ll m;
	cin >> n >> k >> m;
	vector<ll> rocks(n);