Submission #386158

#	Time	Username	Problem	Language	Result	Execution time	Memory
386158		pit4h	Sparklers (JOI17_sparklers)	C++14	100 / 100	96 ms	3436 KiB

sparklers

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

bool solve(int n, int k, ll t, vector<ll> x) {
	int l = k, r = k, L=k, R = k;	
	deque<int> monoL, monoR, MonoL, MonoR;
	monoL.push_back(k), monoR.push_back(k);
	MonoL.push_back(k), MonoR.push_back(k);
	for(int i=0; i<n; ++i) {
		while(l > 0 && (R-l+1) * t - (x[R] - x[l-1]) / 2 >= 0LL) {
			l--;
			while(monoL.size() && (k-l) * t + x[l] / 2 < (k-monoL.back()) * t + x[monoL.back()] / 2) {
				monoL.pop_back();
			}
			monoL.push_back(l);
			while(MonoL.size() && (k-l) * t + x[l] / 2 > (k-MonoL.back()) * t + x[MonoL.back()] / 2) {
				MonoL.pop_back();
			}
			MonoL.push_back(l);
			if((k-l) * t + x[l] / 2 > (k-L) * t + x[L] / 2) {
				L = l;
			}
		}
		while(r < n-1 && (r-L+1) * t - (x[r+1] - x[L]) / 2 >= 0LL) {
			r++;
			while(monoR.size() && (r-k) * t - x[r] / 2 < (monoR.back()-k) * t - x[monoR.back()] / 2) {
				monoR.pop_back();	
			}
			monoR.push_back(r);
			while(MonoR.size() && (r-k) * t - x[r] / 2 > (MonoR.back()-k) * t - x[MonoR.back()] / 2) {
				MonoR.pop_back();	
			}
			MonoR.push_back(r);
			if((r-k) * t - x[r] / 2 > (R-k) * t - x[R] / 2) {
				R = r;
			}
		}
	}
	if(l > 0 || r < n-1) return false;
	
	while(monoL.front() > L) monoL.pop_front();
	while(monoR.front() < R) monoR.pop_front();
	while(MonoL.size() && MonoL.front() >= L) MonoL.pop_front();
	while(MonoR.size() && MonoR.front() <= R) MonoR.pop_front();

	for(int i=0; i<n; ++i) {
		while(L > 0 && (k-MonoL.front()) * t + x[MonoL.front()] / 2 + (monoR.front()-k) * t - x[monoR.front()] / 2 >= 0LL) {
			L = MonoL.front();			
			while(monoL.front() > L) monoL.pop_front();
			while(MonoL.size() && MonoL.front() >= L) MonoL.pop_front();
		}
		while(R < n-1 && (MonoR.front()-k) * t - x[MonoR.front()] / 2 + (k-monoL.front()) * t + x[monoL.front()] / 2 >= 0LL) {
			R = MonoR.front();
			while(monoR.front() < R) monoR.pop_front();
			while(MonoR.size() && MonoR.front() <= R) MonoR.pop_front();
		}
	}
	return L == 0 && R == n-1;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k;
	ll t;
	cin>>n>>k>>t;
	k--;
	t *= 2LL;
	vector<ll> x(n);
	for(int i=0; i<n; ++i) {
		cin>>x[i];
		x[i] *= 2LL;
	}

	ll lo = 0, hi = 1e10 / t + 1;
	while(lo<=hi) {
		ll mid = (lo+hi)/2LL;
		if(solve(n, k, t*mid, x)) {
			hi = mid-1;
		}
		else {
			lo = mid+1;
		}
	}
	cout<<hi+1<<'\n';
}

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