Submission #685042

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
685042	2023-01-23T06:27:49 Z	amunduzbaev	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	624 ms	60856 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	328 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	50 ms	6176 KB	Output is correct
11	Correct	62 ms	7880 KB	Output is correct
12	Correct	29 ms	3916 KB	Output is correct
13	Correct	617 ms	60856 KB	Output is correct
14	Correct	617 ms	60684 KB	Output is correct
15	Correct	615 ms	58700 KB	Output is correct
16	Correct	615 ms	59760 KB	Output is correct
17	Correct	623 ms	59768 KB	Output is correct
18	Correct	617 ms	60524 KB	Output is correct
19	Correct	624 ms	60752 KB	Output is correct
20	Correct	322 ms	33560 KB	Output is correct