/** 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});
}
for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<endl;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
