Submission #684113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684113	2023-01-20T12:28:47 Z	vovamr	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	325 ms	65536 KB

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); }

#define int long long

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

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

	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>>::iterator nxt, prev;

	set<array<int,2>> active;
	for (auto it = segs.begin(); it != segs.end(); ++it) {
		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,2>{ get_len(l, r), l } );
		}
	}

	ve<array<int,3>> nw;

	ll ans = 0;

	while (k && sz(active)) {
		auto [len, l] = *active.begin();
		int r = (l + len - 1 + n) % n;
		active.erase(active.begin());

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

		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);
		assert(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});
		if (make_tuple(rp, lp, vp) != make_tuple(rn, ln, vn)) segs.erase(array<int,3>{rp, lp, vp});
		else {
			break;
		}

		vc += can;

		nw.clear();
		nw.shrink_to_fit();

		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});
			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) {
				active.insert( array<int,2>{ get_len(l, r), l } );
			}
		}
	}

	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

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	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 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	34 ms	7380 KB	Output is correct
11	Correct	40 ms	9440 KB	Output is correct
12	Correct	21 ms	4196 KB	Output is correct
13	Runtime error	325 ms	65536 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-