Submission #1294948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294948		kian2009	Sparklers (JOI17_sparklers)	C++20	0 / 100	2094 ms	572 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

ll n, k, t, x[MAXN], X[MAXN];

void input() {
	cin >> n >> k >> t;
	--k;
	for (int i = 0; i < n; i++)
		cin >> x[i];	
}

bool check(ll s) {
	for (ll i = 0; i < n; i++)
		X[i] = x[i] - 2 * s * t * i;
	ll ma1 = k, ma2 = k;
	for (int i = k; i >= 0; i--)
		if (X[i] >= X[ma1])
			ma1 = i;
	for (int i = k; i < n; i++)
		if (X[i] <= X[ma2])
			ma2 = i;
	ll l = k, r = k;
	while (true) {
		bool has = false;
		ll l1 = l;
		while (true) {
			if (l1 - 1 >= ma1 && X[l1 - 1] >= X[r])
				l1--;
			if (X[l1] >= X[l] || l1 == ma1)
				break;
		}
		if (X[l1] >= X[l] && l1 < l) {
			has = true;
			l = l1;
		}
		ll r1 = r;
		while (true) {
			if (r1 + 1 <= ma2 && X[r1 + 1] <= X[l])
				r1++;
			if (X[r1] <= X[r] || r1 == ma2)
				break;
		}
		if (X[r1] <= X[r] && r1 > r) {
			has = true;
			r = r1;	
		}
		if (!has)
			break;
	}
	if ((l != ma1 || r != ma2) || X[0] < X[n - 1])
		return false;
	l = 0; r = n - 1;
	while (true) {
		bool has = false;
		ll l1 = l;
		while (true) {
			if (l1 + 1 <= ma1 && X[l1 + 1] >= X[r])
				l1++;
			if (X[l1] >= X[l] || l1 == ma1)
				break;
		}
		if (X[l1] >= X[l] && l1 > l) {
			has = true;
			l = l1;
		}
		ll r1 = r;
		while (true) {
			if (r1 - 1 >= ma2 && X[r1 - 1] <= X[l])
				r1--;
			if (X[r1] <= X[r] || r1 == ma2)
				break;
		}
		if (X[r1] <= X[r] && r1 < r) {
			has = true;
			r = r1;	
		}
		if (!has)
			break;
	}
	return (l == ma1 && r == ma2);
}

ll findAns() {
	ll l = -1, r = x[n - 1];
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	cout << findAns() << endl;
	return 0;
}

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