제출 #506136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
506136		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;
set <pair<ll, int>> avl, avr;
multiset <ll> mnl, mnr;

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

inline bool check(ll s){
	if(s * t > 2e9)
		return true;
	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;
		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;
			}
		}
		if(!re){
			avl.clear();
			avr.clear();
			mnl.clear();
			mnr.clear();
				
			for(int i = 0; i <= l; i++){
				avl.insert({-cur[i], i});
				mnl.insert(-w[i]);
				if(w[i] > exr)
					return false;
			}
			for(int i = r; i < n; i++){
				avr.insert({-cur[i], i});
				mnr.insert(-w[i]);
				if(w[i] > exl)
					return false;
			}
			
			while(l >= 0 || r < n){
				bool re = false;
					
				while(l >= 0 && (r == n || exl + -1 * (avl.begin()->fi) >= -1 * (*mnr.begin()))){
					exl += val[l];
					int v = avl.begin() ->se;
					while(l >= v){
						avl.erase({-cur[l], l});
						mnl.erase(mnl.find(-w[l]));
						l--;
					}
					re = true;
				}
				while(r < n && (l < 0 || exr + -1 * (avr.begin()->fi) >= -1 * (*mnl.begin()))){
					exr += val[r];
					int v = avr.begin() ->se;
					while(r <= v){
						avr.erase({-cur[r], r});
						mnr.erase(mnr.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