Submission #864765

#	Time	Username	Problem	Language	Result	Execution time	Memory
864765		manizare	Sparklers (JOI17_sparklers)	C++14	100 / 100	107 ms	13284 KiB

sparklers

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
 
constexpr ll inf = 1e18, N = 2e5 + 10, mod = 1e9 + 7, pr = 1000696969;
 
int n, k;
ll x[N], spA[N], spB[N];
 
bool valid(vector<ll> vc1, vector<ll> vc2) {
	int sa = Sz(vc1), sb = Sz(vc2);
	if(vc1[sa - 1] + vc2[sb - 1] < 0) return 0;
 
	int pa = 0, pb = 0, main_pa = 0;
		
	while((pa < sa - 1) || (pb < sb - 1)) {
		if(vc1[pa] + vc2[pb] < 0) return 0;
		if(pa == sa - 1) {
			pb++;
			continue;
		}
		if(pb == sb - 1) {
			pa++;
			continue;
		}
		int fr = pa;
		main_pa = max(main_pa, pa + 1);
		for(; main_pa < sa; main_pa++) {
			if(vc1[main_pa] + vc2[pb] < 0) break;
			if(vc1[main_pa] - vc1[pa] >= 0) {
				pa = main_pa;
				continue;
			}
		}
		if(pa != fr) continue;
 
		int main_pb = pb;
		for(int i = main_pb + 1; i < sb; i++) {
			if(vc2[i] + vc1[pa] < 0) break;
			if(vc2[i] - vc2[pb] >= 0) {
				main_pb = i;
				break;
			}
		}
 
		if(main_pb > pb) {
			pb = main_pb;
			continue;
		}
 
 
		return 0;
	}
 
	return 1;
}
 
bool okay(ll t) {
	if(t > 1e9) return 1;
	vector<ll> A = {t}, B;
	for(int i = k + 1; i <= n; i++) {
		A.push_back(-(x[i] - x[i - 1]));
		A.push_back(t);
	}
	for(int i = k - 1; i > 0; i--) {
		B.push_back(-(x[i + 1] - x[i]));
		B.push_back(t);
	}
 
	spA[0] = spA[0] = 0;
	for(int i = 0; i < Sz(A); i++) spA[i + 1] = spA[i] + A[i];
	for(int i = 0; i < Sz(B); i++) spB[i + 1] = spB[i] + B[i];
 
	int inda = max_element(spA, spA + Sz(A) + 1) - spA;
	int indb = max_element(spB, spB + Sz(B) + 1) - spB;
 
	vector<ll> lA, rA, lB, rB;
	for(int i = 0; i <= inda; i++) lA.push_back(spA[i]);
	for(int i = inda; i <= Sz(A); i++) rA.push_back(spA[i]);
	for(int i = 0; i <= indb; i++) lB.push_back(spB[i]);
	for(int i = indb; i <= Sz(B); i++) rB.push_back(spB[i]);
 
	reverse(All(rA)), reverse(All(rB));
	
	return valid(lA, lB) && valid(rA, rB);
}
 
int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
	
	ll t; 
	cin >>n >>k >>t;
	for(int i = 1; i <= n; i++) cin >>x[i];
	
 
	int l = 0, r = 1e9;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(okay(1ll * t * mid * 2)) r = mid;
		else l = mid + 1;
	}
 
	cout<<l;
 
 
 
    return 0;
}
 

Compilation message (stderr)

sparklers.cpp: In function 'bool okay(ll)':
sparklers.cpp:79:9: warning: operation on 'spA[0]' may be undefined [-Wsequence-point]
   79 |  spA[0] = spA[0] = 0;
      |  ~~~~~~~^~~~~~~~~~~~

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