Submission #684128

#	Time	Username	Problem	Language	Result	Execution time	Memory
684128		vovamr	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	115 ms	33372 KiB

route

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e6 + 100;

int p[N], rnk[N];
int l[N], r[N];
int v[N];

int a[N];

int n;

inline void make(int i) {
	p[i] = i, rnk[i] = 1;
	l[i] = r[i] = i;
	v[i] = a[i];
}

inline int par(int v) {
	if (p[v] == v) return v;
	return (p[v] = par(p[v]));
}

inline bool uni(int a, int b) {
	a = par(a), b = par(b);
	if (a == b) return 0;
	if (rnk[a] > rnk[b]) swap(a, b);

	int la, ra, va, lb, rb, vb;
	tie(la, ra, va) = make_tuple(l[a], r[a], v[a]);
	tie(lb, rb, vb) = make_tuple(l[b], r[b], v[b]);

	p[a] = b;
	rnk[b] += rnk[a];

	if ((ra + 1) % n == lb) tie(l[b], r[b]) = mpp(la, rb);
	else if ((rb + 1) % n == la) tie(l[b], r[b]) = mpp(lb, ra);
	if ((r[b] + 1) % n == l[b]) tie(l[b], r[b]) = mpp(0, n - 1);
	v[b] = max(v[b], v[a]);
	return 1;
}

inline void solve() {
	int k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) cin >> a[i];

	auto get_len = [](int l, int r) {
		int ans = (l <= r ? r - l + 1 : (n - 1 - l + 1) + r + 1);
		return ans;
	};

	if (*max_element(a, a + n) == *min_element(a, a + n)) {
		cout << 0;
		return;
	}

	for (int i = 0; i < n; ++i) make(i);
	for (int i = 0; i < n; ++i) if (a[i] == a[(i + 1) % n]) uni(i, (i + 1) % n);

	set<array<int,3>> active;
	for (int i = 0; i < n; ++i) {
		if (par(i) == i) {

			int le = l[i];
			int re = r[i];

			int pr = (le - 1 + n) % n;
			int nx = (re + 1) % n;

			if (v[par(pr)] > v[i] && v[par(nx)] > v[i]) {
				active.insert({get_len(l[i], r[i]), l[i], r[i]});
			}
		}
	}

	ll ans = 0;
	while (k && sz(active)) {
		auto [len, l, r] = *active.begin();
		active.erase(active.begin());

		int pr = (l - 1 + n) % n;
		int nx = (r + 1) % n;

		int vn = v[par(nx)];
		int vp = v[par(pr)];

		int can = min(k / len, min(vn, vp) - v[par(l)]);

		if (!can) break;

		ans += 2 * can;

		k -= can * len;
		v[par(l)] += can;

		if (v[par(l)] == v[par(pr)]) uni(l, pr);
		if (v[par(l)] == v[par(nx)]) uni(l, nx);

		for (int i : {pr, l, nx}) {
			i = par(i);
			if (par(i) == i) {
				int le = ::l[i];
				int re = ::r[i];

				int pr = (le - 1 + n) % n;
				int nx = (re + 1) % n;

				if (v[par(pr)] > v[i] && v[par(nx)] > v[i]) {
					active.insert({get_len(::l[i], ::r[i]), ::l[i], ::r[i]});
				}
			}
		}
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

• Subtask 1: 100 / 100