#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 1e6 + 100;
int p[N], rnk[N];
int l[N], r[N];
int v[N];
int a[N];
int n;
inline void make(int i) {
p[i] = i, rnk[i] = 1;
l[i] = r[i] = i;
v[i] = a[i];
}
inline int par(int v) {
if (p[v] == v) return v;
return (p[v] = par(p[v]));
}
inline bool uni(int a, int b) {
a = par(a), b = par(b);
if (a == b) return 0;
if (rnk[a] > rnk[b]) swap(a, b);
int la, ra, va, lb, rb, vb;
tie(la, ra, va) = make_tuple(l[a], r[a], v[a]);
tie(lb, rb, vb) = make_tuple(l[b], r[b], v[b]);
p[a] = b;
rnk[b] += rnk[a];
if ((ra + 1) % n == lb) tie(l[b], r[b]) = mpp(la, rb);
else if ((rb + 1) % n == la) tie(l[b], r[b]) = mpp(lb, ra);
if ((r[b] + 1) % n == l[b]) tie(l[b], r[b]) = mpp(0, n - 1);
v[b] = max(v[b], v[a]);
return 1;
}
inline void solve() {
int k;
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
auto get_len = [](int l, int r) {
int ans = (l <= r ? r - l + 1 : (n - 1 - l + 1) + r + 1);
return ans;
};
if (*max_element(a, a + n) == *min_element(a, a + n)) {
cout << 0;
return;
}
for (int i = 0; i < n; ++i) make(i);
for (int i = 0; i < n; ++i) if (a[i] == a[(i + 1) % n]) uni(i, (i + 1) % n);
set<array<int,3>> active;
for (int i = 0; i < n; ++i) {
if (par(i) == i) {
int le = l[i];
int re = r[i];
int pr = (le - 1 + n) % n;
int nx = (re + 1) % n;
if (v[par(pr)] > v[i] && v[par(nx)] > v[i]) {
active.insert({get_len(l[i], r[i]), l[i], r[i]});
}
}
}
ll ans = 0;
while (k && sz(active)) {
auto [len, l, r] = *active.begin();
active.erase(active.begin());
int pr = (l - 1 + n) % n;
int nx = (r + 1) % n;
int vn = v[par(nx)];
int vp = v[par(pr)];
int can = min(k / len, min(vn, vp) - v[par(l)]);
if (!can) break;
ans += 2 * can;
k -= can * len;
v[par(l)] += can;
if (v[par(l)] == v[par(pr)]) uni(l, pr);
if (v[par(l)] == v[par(nx)]) uni(l, nx);
for (int i : {pr, l, nx}) {
i = par(i);
if (par(i) == i) {
int le = ::l[i];
int re = ::r[i];
int pr = (le - 1 + n) % n;
int nx = (re + 1) % n;
if (v[par(pr)] > v[i] && v[par(nx)] > v[i]) {
active.insert({get_len(::l[i], ::r[i]), ::l[i], ::r[i]});
}
}
}
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 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 |
12 ms |
2676 KB |
Output is correct |
| 11 |
Correct |
19 ms |
4724 KB |
Output is correct |
| 12 |
Correct |
11 ms |
2680 KB |
Output is correct |
| 13 |
Correct |
108 ms |
33112 KB |
Output is correct |
| 14 |
Correct |
112 ms |
33372 KB |
Output is correct |
| 15 |
Correct |
100 ms |
31404 KB |
Output is correct |
| 16 |
Correct |
107 ms |
32328 KB |
Output is correct |
| 17 |
Correct |
104 ms |
32332 KB |
Output is correct |
| 18 |
Correct |
108 ms |
33144 KB |
Output is correct |
| 19 |
Correct |
115 ms |
33308 KB |
Output is correct |
| 20 |
Correct |
92 ms |
29664 KB |
Output is correct |
