Submission #684104

# Submission time Handle Problem Language Result Execution time Memory
684104 2023-01-20T11:59:07 Z vovamr Mountain Trek Route (IZhO12_route) C++17
0 / 100
330 ms 65536 KB
#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); }

inline void solve() {
	int n, k;
	cin >> n >> k;

	auto get_len = [&n](int l, int r) {
		if (l <= r) return r - l + 1;
		else return n - (l - r) + 1;
	};

	ve<int> a(n);
	for (auto &i : a) cin >> i;

	if (*max_element(all(a)) == *min_element(all(a))) {
		cout << 0;
		return;
	}

	set<array<int,3>> segs;
	{
		int ptr = n;
		while (ptr - 1 >= 0 && a[ptr - 1] == a[0]) --ptr;
		
		int L = (ptr == n ? 0 : ptr);
		for (int i = 0; i < n; ) {
			if (i >= ptr) break;

			int j = i;
			while (j < n && a[j] == a[i]) ++j;

			segs.insert(array<int,3>{j - 1, i == 0 ? L : i, a[i]});
			i = j;
		}
	}

	set<array<int,3>> active;
	for (auto it = segs.begin(); it != segs.end(); ++it) {
		set<array<int,3>>::iterator nxt, prev;
		if (it == --segs.end()) nxt = segs.begin();
		else nxt = it, ++nxt;

		if (it == segs.begin()) prev = --segs.end();
		else prev = it, --prev;

		int vp = (*prev)[2];
		int vn = (*nxt)[2];
		int vc = (*it)[2];

		if (vp > vc && vn > vc) {
			auto &[r, l, x] = *it;
			active.insert( array<int,3>{ get_len(l, r), l, r } );
		}
	}

	ll ans = 0;

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

		auto it = segs.lower_bound(array<int,3>{r, l, -iinf});
		set<array<int,3>>::iterator prev, nxt;

		if (it == --segs.end()) nxt = segs.begin();
		else nxt = it, ++nxt;
		if (it == segs.begin()) prev = --segs.end();
		else prev = it, --prev;

		auto [rp, lp, vp] = *prev;
		auto [rn, ln, vn] = *nxt;

		int vc = (*it)[2];

		int can = min(k / len, min(vp, vn) - vc);
		if (!can) break;

		k -= can * len;
		ans += 2 * can;

		segs.erase(array<int,3>{r, l, vc});
		segs.erase(array<int,3>{rn, ln, vn});
		segs.erase(array<int,3>{rp, lp, vp});

		vc += can;
		ve<array<int,3>> nw;
		if (vp != vc) {
			nw.pb({rp, lp, vp});
			if (vc != vn) {
				nw.pb({r, l, vc});
				nw.pb({rn, ln, vn});
			}
			else {
				nw.pb({rn, l, vc});
			}
		}
		else if (vp == vc && vc != vn) {
			nw.pb({r, lp, vc});
			nw.pb({rn, ln, vn});
		}
		else {
			nw.pb({rn, l, vc});
		}

		for (auto &[r, l, x] : nw) {
			segs.insert(array<int,3>{r, l, x});
		}

		for (auto &[r, l, x] : nw) {
			auto it = segs.find({r, l, x});
			set<array<int,3>>::iterator nxt, prev;
			if (it == --segs.end()) nxt = segs.begin();
			else nxt = it, ++nxt;

			if (it == segs.begin()) prev = --segs.end();
			else prev = it, --prev;

			int vp = (*prev)[2];
			int vn = (*nxt)[2];
			int vc = (*it)[2];

			if (vp > vc && vn > vc) {
				auto &[r, l, x] = *it;
				active.insert( array<int,3>{ get_len(l, r), l, r } );
			}
		}
	}

	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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 32 ms 7752 KB Output is correct
11 Correct 45 ms 9972 KB Output is correct
12 Correct 20 ms 4684 KB Output is correct
13 Runtime error 330 ms 65536 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -