Submission #685035

#	Time	Username	Problem	Language	Result	Execution time	Memory
685035		amunduzbaev	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	1 ms	212 KiB

route

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

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 1e6 + 5;
const int MX = 2e9 + 5;
int a[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k; cin >> n >> k;
	set<int> on;
	set<ar<int, 2>> mn;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	if(a[1] != a[n]) on.insert(1);
	for(int i=2;i<=n;i++){
		if(a[i] != a[i - 1]) on.insert(i);
	}
	
	auto to_l = [&](int i){
		//~ for(auto x : on) cout<<x<<" ";
		auto it = on.lower_bound(i);
		//~ cout<<": "<<i<<" "<<*it<<endl;
		assert(it != on.end() && *it == i);
		if(it == on.begin()) return *--on.end();
		return *--it;
	};
	auto to_r = [&](int i){
		auto it = on.upper_bound(i);
		if(it == on.end()) return *on.begin();
		return *it;
	};
	auto check = [&](int i){
		if(a[i] < a[to_l(i)] && a[i] < a[to_r(i)]){
			if(i < to_r(i)) mn.insert({to_r(i) - i, i});
			else mn.insert({n - i + to_r(i), i});
		}
	};
	for(auto i : on){
		check(i);
	}
	
	ll res = 0;
	while(!mn.empty()){
		auto w = (*mn.begin())[0], i = (*mn.begin())[1];
		int l = to_l(i), r = to_r(i);
		int h = min(a[l], a[r]) - a[i];
		if(h * 1ll * w > k){
			res += 2 * (k / w);
			a[i] += k / w;
			break;
		}
		res += 2 * h;
		a[i] += h; k -= h * w;
		mn.erase(mn.begin());
		if(a[l] == a[i] && a[r] == a[i]){
			on.erase(i), on.erase(r);
			if(!on.empty() && l != *on.begin()) check(l);
		}
		else if(a[l] == a[i]){
			on.erase(i);
			if(!on.empty() && l != *on.begin()) check(l);
		}
		else if(a[r] == a[i]){
			on.erase(r);
			if(!on.empty() && i != *on.begin()) check(i);
		}
	}
	
	cout<<res<<"\n";
}

• Subtask 1: 0 / 100