Submission #341632

#	Time	Username	Problem	Language	Result	Execution time	Memory
341632		tengiz05	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	38 ms	11884 KiB

route

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
int l[N], r[N]; // left and right neighbors of the block
struct DSU{
	vector<int> sz, p;
	int numofsets;
	DSU(int nn){
		sz.assign(nn,1);
		p.assign(nn, 0);
		for(int i=0;i<nn;i++)p[i]=i;
	}
	int par(int u){
		if(p[u] == u)return u;
		return p[u] = par(p[u]);
	}
	void merge(int u, int v){
		u = par(u);v = par(v);
		if(u == v)return;
		numofsets--;
		p[v] = u;
		sz[u] += sz[v];
		r[u] = r[v];
		l[v] = l[u];
	}
	int size(int u){u = par(u);return sz[par(u)];}
}dsu(N);
int get(int u){
	return dsu.par(u);
}
void solve(int test_case){
	int i, j;
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> a[i];
	}
	dsu.numofsets = n;
	l[1] = n;
	r[1] = 2;
	l[n] = n-1;
	r[n] = 1;
	for(i=2;i<n;i++){
		l[i] = i-1;
		r[i] = i+1;
	}
	a[n+1] = a[1];
	a[0] = a[n];
	int answer = 0;
	for(i=1;i<=n;i++){
		if(a[i] == a[r[i]])dsu.merge(i, r[i]);
	}
	priority_queue<pii, vector<pii>, greater<pii>> q;
	vector<pii> tmp;
	for(i=1;i<=n;i++){
		if(dsu.par(i) == i && a[l[i]+1] < a[l[i]] && a[r[i]-1] < a[r[i]]){
			q.push({dsu.size(i),i});
			tmp.pb({dsu.size(i),i});
		}
	}
	while(!q.empty()){
		auto [S, idx] = q.top();q.pop();
		i = get(idx);
		int mn = min(a[get(l[i])], a[get(r[i])]);
		if((mn-a[i])*S <= k){
			k -= (mn-a[i])*S;
			answer += 2*(mn-a[i]);
			a[i] += mn-a[i];
			if(a[i] == a[get(l[i])])dsu.merge(get(l[i]), i);
			if(a[i] == a[get(r[i])])dsu.merge(i, get(r[i]));
			i = get(i);
			mn = min(a[get(l[i])], a[get(r[i])]);
			if(mn > a[i])q.push({dsu.size(i), i});
		}else {
			answer += 2*(k/S);
			break;
		}
	}
	cout << answer << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message (stderr)

route.cpp: In function 'void solve(long long int)':
route.cpp:45:9: warning: unused variable 'j' [-Wunused-variable]
   45 |  int i, j;
      |         ^

• Subtask 1: 0 / 100