#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); }
#define int long long
inline void ass(bool condition) {
if (!condition) {
while (1) {
}
}
}
inline void solve() {
int n, k;
cin >> n >> k;
auto get_len = [&n](int l, int r) {
int ans = (l <= r ? r - l + 1 : n - (l - r) + 1);
assert(r == (l + ans - 1 + n) % n);
return ans;
};
ve<int> a(n);
for (auto &i : a) cin >> i;
if (*max_element(all(a)) == *min_element(all(a))) {
cout << 0;
return;
}
set<array<int,3>> segs;
{
int ptr = n;
while (ptr - 1 >= 0 && a[ptr - 1] == a[0]) --ptr;
int L = (ptr == n ? 0 : ptr);
for (int i = 0; i < n; ) {
if (i >= ptr) break;
int j = i;
while (j < n && a[j] == a[i]) ++j;
segs.insert(array<int,3>{j - 1, i == 0 ? L : i, a[i]});
i = j;
}
}
set<array<int,3>>::iterator nxt, prev;
set<array<int,2>> active;
for (auto it = segs.begin(); it != segs.end(); ++it) {
if (it == --segs.end()) nxt = segs.begin();
else nxt = it, ++nxt;
if (it == segs.begin()) prev = --segs.end();
else prev = it, --prev;
int vp = (*prev)[2];
int vn = (*nxt)[2];
int vc = (*it)[2];
if (vp > vc && vn > vc) {
auto &[r, l, x] = *it;
active.insert( array<int,2>{ get_len(l, r), l } );
}
}
ve<array<int,3>> nw;
ll ans = 0;
while (k && sz(active)) {
ass(sz(segs) >= 2);
auto [len, l] = *active.begin();
int r = (l + len - 1 + n) % n;
active.erase(active.begin());
auto it = segs.lower_bound(array<int,3>{r, l, -iinf});
ass((*it)[0] == r && (*it)[1] == l);
if (it == --segs.end()) nxt = segs.begin();
else nxt = it, ++nxt;
if (it == segs.begin()) prev = --segs.end();
else prev = it, --prev;
auto [rp, lp, vp] = *prev;
auto [rn, ln, vn] = *nxt;
int vc = (*it)[2];
int can = min(k / len, min(vp, vn) - vc);
ass(min(vp, vn) > vc);
if (!can) break;
k -= can * len; ans += 2 * can;
segs.erase(array<int,3>{r, l, vc});
segs.erase(array<int,3>{rn, ln, vn});
if (make_tuple(rp, lp, vp) != make_tuple(rn, ln, vn)) segs.erase(array<int,3>{rp, lp, vp});
else {
break;
}
vc += can;
nw.clear();
nw.shrink_to_fit();
if (vp != vc) {
nw.pb({rp, lp, vp});
if (vc != vn) {
nw.pb({r, l, vc});
nw.pb({rn, ln, vn});
}
else {
nw.pb({rn, l, vc});
}
}
else if (vp == vc && vc != vn) {
nw.pb({r, lp, vc});
nw.pb({rn, ln, vn});
}
else {
nw.pb({rn, l, vc});
}
for (auto &[r, l, x] : nw) {
segs.insert(array<int,3>{r, l, x});
}
for (auto &[r, l, x] : nw) {
auto it = segs.lower_bound({r, l, x});
ass((*it)[0] == r && (*it)[1] == l && (*it)[2] == x);
if (it == --segs.end()) nxt = segs.begin();
else nxt = it, ++nxt;
if (it == segs.begin()) prev = --segs.end();
else prev = it, --prev;
int vp = (*prev)[2];
int vn = (*nxt)[2];
int vc = (*it)[2];
if (vp > vc && vn > vc) {
active.insert( array<int,2>{ get_len(l, r), l } );
}
}
}
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 |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 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 |
33 ms |
7352 KB |
Output is correct |
| 11 |
Correct |
43 ms |
9432 KB |
Output is correct |
| 12 |
Correct |
19 ms |
4232 KB |
Output is correct |
| 13 |
Runtime error |
303 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Halted |
0 ms |
0 KB |
- |
