Submission #1225854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225854		siewjh	Sparklers (JOI17_sparklers)	C++20	100 / 100	123 ms	13620 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int MAXN = 100005;
const i128 inf = 1e36;
i128 val[MAXN], inlm[MAXN], inrm[MAXN], oulm[MAXN], ourm[MAXN];
ll pos[MAXN], T;
int inl[MAXN], inr[MAXN], oul[MAXN], our[MAXN], N, K;
ll cdiv(ll a, ll b){
	return (a + b - 1) / b;
}
bool test(ll v){
	for (int i = 1; i <= N; i++) val[i] = pos[i] - (i128)(2) * v * T * i;
	int bl, br;
	vector<pair<i128, int>> st;
	for (int i = 1; i <= K; i++){
		while (!st.empty() && st.back().first < val[i]) st.pop_back();
		if (!st.empty()) oul[i] = st.back().second;
		st.push_back({val[i], i});
	}
	bl = st[0].second; st.clear();
	for (int i = N; i >= K; i--){
		while (!st.empty() && st.back().first > val[i]) st.pop_back();
		if (!st.empty()) our[i] = st.back().second;
		st.push_back({val[i], i});
	}
	br = st[0].second; st.clear();
	for (int i = K; i >= 1; i--){
		while (!st.empty() && st.back().first < val[i]) st.pop_back();
		if (!st.empty()) inl[i] = st.back().second;
		st.push_back({val[i], i});
	}
	st.clear();
	for (int i = K; i <= N; i++){
		while (!st.empty() && st.back().first > val[i]) st.pop_back();
		if (!st.empty()) inr[i] = st.back().second;
		st.push_back({val[i], i});
	}
	st.clear();
	i128 mv = inf;
	for (int i = K; i >= 1; i--){
		mv = min(mv, val[i]); oulm[i] = mv;
	}
	mv = -inf;
	for (int i = K; i <= N; i++){
		mv = max(mv, val[i]); ourm[i] = mv;
	}
	mv = inf;
	for (int i = 1; i <= K; i++){
		mv = min(mv, val[i]); inlm[i] = mv;
	}
	mv = -inf;
	for (int i = N; i >= K; i--){
		mv = max(mv, val[i]); inrm[i] = mv;
	}
	int l = K, r = K;
	while (l != bl || r != br){
		bool ok = 0;
		if (l != bl){
			int nl = oul[l];
			if (oulm[nl] >= val[r]){
				ok = 1; l = nl;
			}
		}
		if (!ok && r != br){
			int nr = our[r];
			if (val[l] >= ourm[nr]){
				ok = 1; r = nr;
			}
		}
		if (!ok) return 0;
	}
	if (val[1] < val[N]) return 0;
	l = 1, r = N;
	while (l != bl || r != br){
		bool ok = 0;
		if (l != bl){
			int nl = inl[l];
			if (inlm[nl] >= val[r]){
				ok = 1; l = nl;
			}
		}
		if (!ok && r != br){
			int nr = inr[r];
			if (val[l] >= inrm[nr]){
				ok = 1; r = nr;
			}
		}
		if (!ok) return 0;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K >> T;
	for (int i = 1; i <= N; i++) cin >> pos[i];
	ll lo = 0, hi = 1e9, ans;
	while (lo <= hi){
		ll m = (lo + hi) >> 1;
		if (test(m)){
			ans = m; hi = m - 1;
		}
		else lo = m + 1;
	}
	cout << ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50