Submission #686099

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
686099	2023-01-25T05:45:43 Z	pragmatist	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	272 ms	65536 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];
pair<int, int> 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;
	l[v] = min(l[v], l[u]);
	r[v] = max(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] = l[i].x = r[i].x = i;
		if(i == 1) l[i].y = n;
		else l[i].y = i - 1;

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

	ll ans = 0;
	while(!s.empty()) {
		int x = s.begin() -> y;
		s.erase(s.begin());
		
		if(sz[x] == n) break;
		int L = get(l[x].y), R = get(r[x].y);
		
		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.insert({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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	324 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	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	34 ms	9000 KB	Output is correct
11	Correct	32 ms	9084 KB	Output is correct
12	Correct	22 ms	7184 KB	Output is correct
13	Runtime error	272 ms	65536 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-