제출 #506066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
506066		fatemetmhr	Sparklers (JOI17_sparklers)	C++17	0 / 100	1 ms	332 KiB

sparklers

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

ll n, k, t;
multiset <ll> avl, avr;

ll x[maxn5], cur[maxn5];
ll val[maxn5], w[maxn5];

inline bool check(ll s){
	for(int i = k - 1; i >= 0; i--){
		val[i] = 2 * s * t - x[i + 1] + x[i];
		cur[i] = val[i] + cur[i + 1];
		w[i] = x[i + 1] - x[i] - cur[i + 1];
	}
	for(int i = k + 1; i < n; i++){
		val[i] = 2 * s * t - x[i] + x[i - 1];
		cur[i] = val[i] + cur[i - 1];
		w[i] = x[i] - x[i - 1] - cur[i - 1];
	}
	cur[k] = 0;
	
	int l = k - 1, r = k + 1, lq = k - 1, rq = k + 1;
	ll lim = 2 * t * s;
	ll lqsum = 0, rqsum = 0;
	ll exl = lim, exr = lim;
	while(l >= 0 || r < n){
		bool re = false;
		//cout << "* " << s << ' ' << l << ' ' << r << ' ' << exl << ' ' << exr << ' ' << val[r] << ' ' << w[l] << '\n';
		while(lq >= 0 && w[lq] <= exr){
			lqsum += val[lq];
			lq--;
			if(lqsum >= 0){
				exl += lqsum;
				lqsum = 0;
				l = lq;
				re = true;
			}
		}
		while(rq < n && w[rq] <= exl){
			rqsum += val[rq];
			rq++;
			if(rqsum >= 0){
				exr += rqsum;
				rqsum = 0;
				r = rq;
				re = true;
			}
		}
		//cout << "ok " << re << '\n';
		if(!re){
			avl.clear();
			avr.clear();
				
			for(int i = 0; i <= l; i++)
				avl.insert(-w[i]);
			for(int i = r; i < n; i++)
				avr.insert(-w[i]);
			
			while(l >= 0 || r < n){
				bool re = false;
				while(l >= 0 && w[l] <= exr && (r == n || exl + val[l] >= -1 * (*avr.begin()))){
					exl += val[l];
					avl.erase(avl.find(-w[l]));
					l--;
					re = true;
				}
				while(r < n && w[r] <= exl && (l < 0 || exr + val[r] >= -1 * (*avl.begin()))){
					exr += val[r];
					avr.erase(avr.find(-w[r]));
					r++;
					re = true;
				}
				if(!re)
					return false;
			}
			break;
		}
	}
	return true;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


	cin >> n >> k >> t;
	k--;
	for(int i = 0; i < n; i++)
		cin >> x[i];
	ll lo = -1, hi = 1e9 + 1;
	while(hi - lo > 1){
		ll mid = (lo + hi) >> 1;
		if(check(mid))
			hi = mid;
		else 
			lo = mid;
	}
	
	cout << hi << endl;	
	
}

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