Submission #686126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
686126	2023-01-25T05:56:06 Z	pragmatist	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	296 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], 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]);
		}
	}
	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]), 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.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	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 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	31 ms	7380 KB	Output is correct
11	Correct	32 ms	7384 KB	Output is correct
12	Correct	24 ms	5548 KB	Output is correct
13	Runtime error	296 ms	65536 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-