Submission #685042

#	Time	Username	Problem	Language	Result	Execution time	Memory
685042		amunduzbaev	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	624 ms	60856 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];

void usaco(string s){
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	//~ usaco("g");
	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);
		assert(a[i] != a[to_l(i)] && a[i] != a[to_r(i)]);
	}
	
	ll res = 0;
	while(!mn.empty()){
		//~ for(auto x : on) cout<<a[x]<<" ";
		//~ cout<<"\n";
		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];
		//~ cout<<h<<" "<<w<<" "<<k<<"\n";
		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());
		//~ cout<<l<<" "<<r<<"\n";
		if(l == r) break;
		if(a[l] == a[i] && a[r] == a[i]){
			on.erase(i), on.erase(r);
			check(l);
		}
		else if(a[l] == a[i]){
			on.erase(i);
			check(l);
		}
		else if(a[r] == a[i]){
			on.erase(r);
			check(i);
		}
	}
	
	cout<<res<<"\n";
}

Compilation message (stderr)

route.cpp: In function 'void usaco(std::string)':
route.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
route.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100