Submission #686131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
686131	2023-01-25T05:58:24 Z	pragmatist	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	225 ms	43940 KB

route

/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include<bits/stdc++.h>
 
#define ld long double
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;

const int N = (int)1e6 + 7; // make sure this is right
const int M = (int)1e6 + 7;
const int inf = (int)2e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

int mult(int x, int y) {
	return 1ll * x * y % MOD;
}

int n, k, a[N], b[N];
int sz[N], p[N], l[N], r[N];

int get(int v) {
	return (v == p[v] ? v : p[v] = get(p[v]));
}

void comb(int u, int v) {
	u = get(u);
	v = get(v);
	if(u == v) return;
	if(u < v) l[v] = l[u];
	else r[v] = r[u];
	p[u] = v;
	sz[v] += sz[u];
}

void solve() {
	cin >> n >> k;
	int mx = 0;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		if(a[i] > a[mx])
			mx = i;   
	}
	for(int i = mx; i <= n; ++i) b[i - mx + 1] = a[i];
	for(int i = 1; i < mx; ++i) b[n - mx + i + 1] = a[i];
	for(int i = 1; i <= n; ++i)	{
		a[i] = b[i];
	} 
	for(int i = 1; i <= n; ++i) {
		p[i] = i;
		if(i == 1) l[i] = n;
		else l[i] = i - 1;

		if(i == n) r[i] = 1;
		else r[i] = i + 1;
		sz[i] = 1;
	}
	for(int i = 1; i <= n; ++i) {
		if(a[i] == a[r[i]]) {
			comb(i, r[i]);
		}
	}
	priority_queue<pair<int, int> > s;
	for(int i = 1; i <= n; ++i) {
	    int x = get(i);
		s.push({-sz[x], x});	
	}

	ll ans = 0;
	while(!s.empty()) {
		int x = s.top().y;
		s.pop();

		if(sz[x] == n) break;
		int L = get(l[x]), R = get(r[x]);
		
		if(a[x] < a[L] && a[x] < a[R]) {
			int can = min(k / sz[x], min(a[L], a[R]) - a[x]);
			ans += 2 * can;
			k -= can * sz[x];
			a[x] += can;
		    if(can == 0) continue;

		    if(a[x] == a[L]) comb(L, x);
			if(a[x] == a[R]) comb(R, x);
			
			x = get(x);
			s.push({-sz[x], x});
		}
	}
	cout << ans << "\n";
}
	
signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	19 ms	3796 KB	Output is correct
11	Correct	20 ms	3792 KB	Output is correct
12	Correct	18 ms	4436 KB	Output is correct
13	Correct	205 ms	41684 KB	Output is correct
14	Correct	213 ms	41628 KB	Output is correct
15	Correct	198 ms	39768 KB	Output is correct
16	Correct	220 ms	40632 KB	Output is correct
17	Correct	207 ms	40728 KB	Output is correct
18	Correct	225 ms	41604 KB	Output is correct
19	Correct	211 ms	41676 KB	Output is correct
20	Correct	166 ms	43940 KB	Output is correct