Submission #339156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339156	2020-12-24T17:01:29 Z	amunduzbaev	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	140 ms	49004 KB

route

/** made by amunduzbaev **/
#include <bits/stdc++.h>

using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 1e6+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
ll s, n, m, k, ans, a[N];
ll sz[N], par[N], l[N], r[N], total;

int find(int i){
	if(par[i] == i) return i;
	return par[i] = find(par[i]);
}

void merge(int i, int j){
	i = find(i), j = find(j);
	if(i == j) return;
	par[j] = i;
	r[i] = r[j];
	sz[i] += sz[j];
}

void solve(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sz[i] = 1;
		par[i] = i;
		if(i) l[i] = i-1;
		else l[i] = n-1;
		if(i < n-1) r[i] = i+1;
		else r[i] = 0;
	}
	
	for(int i=0;i<n;i++){
		total += abs(a[i] - a[r[i]]);
		if(a[i] == a[r[i]]) merge(i, r[i]);
	}
	priority_queue<pii> q;
	
	for(int i=0;i<n;i++){
		if(par[i] == i && a[i] < min(a[find(l[i])], a[find(r[i])])) q.push({-sz[i], i});
	}
	while(!q.empty()){
		int cur = q.top().ss;
		q.pop();
		ll val = min(a[find(l[cur])], a[find(r[cur])]) - a[cur];
		//cout<<cur<<" "<<val<<" "<<sz[cur]<<"\n";
		if(val*sz[cur] > k){
			ans += 2*(k/sz[cur]);
			k /= sz[cur];
			break;
		}
		k -= sz[cur] * val;
		ans += 2ll*val;
		a[cur] += val;
		if(a[cur] == a[find(l[cur])]) merge(l[cur], cur);
		if(a[cur] == a[find(r[cur])]) merge(cur, r[cur]);
		cur = find(cur);
		//cout<<a[cur]<<" "<<a[find(l[cur])]<<" "<<a[find(r[cur])]<<endl;
		if(a[cur] < min(a[find(l[cur])], a[find(r[cur])])) q.push({-sz[cur], cur});
	}
	
	
	cout<<ans<<"\n";
	return;
}

/*

10 7
2 2 3 1 5 4 4 4 1 4

*/

int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	14 ms	5100 KB	Output is correct
11	Correct	17 ms	5872 KB	Output is correct
12	Correct	14 ms	5228 KB	Output is correct
13	Correct	136 ms	49004 KB	Output is correct
14	Correct	140 ms	48992 KB	Output is correct
15	Correct	127 ms	47084 KB	Output is correct
16	Correct	134 ms	48236 KB	Output is correct
17	Correct	129 ms	48108 KB	Output is correct
18	Correct	135 ms	48876 KB	Output is correct
19	Correct	139 ms	49004 KB	Output is correct
20	Correct	114 ms	45548 KB	Output is correct