#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e6 + 5;
const int LG = 31;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);
vector<int> p(MAX), l(MAX), r(MAX), siz(MAX), val(MAX);
int m = 0;
int n;
void create(int x, int v) {
p[x] = l[x] = r[x] = x;
siz[x] = 1;
val[x] = v;
m++;
}
int get(int x) {
return p[x] = (p[x] == x? x : get(p[x]));
}
void unite(int x, int y) {
x = get(x), y = get(y);
if(x != y) {
val[x] = val[y];
if(siz[x] < siz[y]) swap(x, y);
if(r[x] >= n) {
if(r[y] + 1 == l[x]) l[x] = l[y];
else if(r[x] % n + 1 == l[y]) r[x] = r[y] + n;
}
else if(r[y] >= n) {
if(r[x] + 1 == l[y]) l[y] = l[x];
else if(r[y] % n + 1 == l[x]) r[y] = r[x] + n;
swap(l[x], l[y]);
swap(r[x], r[y]);
}
else if(r[x] + 1 != l[y] && r[y] + 1 != l[x]) {
if(r[x] == n - 1) r[x] = r[y] + n;
else {
l[x] = l[y];
r[x] += n;
}
}
else {
umin(l[x], l[y]);
umax(r[x], r[y]);
}
siz[x] += siz[y];
p[y] = x;
m--;
}
}
void solve() {
int k;
cin >> n >> k;
vector<int> a(n);
for(auto &i : a) {
cin >> i;
}
int ans = 0;
for(int i = 0; i < n; i++) create(i, a[i]);
for(int i = 1; i < n; i++) {
if(a[i] == a[i - 1]) unite(i, i - 1);
}
if(a[0] == a[n - 1]) unite(0, n - 1);
set<pair<int, int>> best;
vector<int> v(n);
vector<int> was(n, 0);
for(int i = 0; i < n; i++) {
if(was[get(i)]) continue;
int ok = 1;
int L = (l[get(i)] - 1 + n) % n, R = (r[get(i)] + 1) % n;
if(a[i] >= a[R]) ok = 0;
if(a[i] >= a[L]) ok = 0;
if(ok) {
best.insert({siz[get(i)], get(i)});
v[get(i)] = siz[get(i)];
}
was[get(i)] = 1;
}
while(sz(best) && k) {
int i = (*best.begin()).s; best.erase(best.begin());
if(siz[get(i)] > k) continue;
if(siz[get(i)] == n) break;
int L = (l[get(i)] - 1 + n) % n, R = (r[get(i)] + 1) % n;
int d = inf;
umin(d, val[get(R)] - val[get(i)]);
umin(d, val[get(L)] - val[get(i)]);
umin(d, k / siz[get(i)]);
ans += 2 * d;
k -= d * siz[get(i)];
val[get(i)] += d;
if(val[get(i)] == val[get(R)]) {
best.erase({v[get(R)], get(R)});
unite(i, R);
}
if(val[get(i)] == val[get(L)]) {
best.erase({v[get(L)], get(L)});
unite(i, L);
}
L = (l[get(i)] - 1 + n) % n, R = (r[get(i)] + 1) % n;
int ok = 1;
if(val[get(i)] >= val[get(R)]) ok = 0;
if(val[get(i)] >= val[get(L)]) ok = 0;
if(ok) {
best.insert({siz[get(i)], get(i)});
v[get(i)] = siz[get(i)];
}
}
cout << ans << '\n';
}
signed main() {
// freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ttt = 1;
// cin >> ttt;
while(ttt--) {
solve();
}
return 0;
}
Compilation message
route.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
8 | #pragma comment (linker, "/STACK: 16777216")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
39380 KB |
Output is correct |
| 2 |
Correct |
18 ms |
39380 KB |
Output is correct |
| 3 |
Correct |
15 ms |
39500 KB |
Output is correct |
| 4 |
Correct |
18 ms |
39464 KB |
Output is correct |
| 5 |
Correct |
15 ms |
39380 KB |
Output is correct |
| 6 |
Correct |
17 ms |
39380 KB |
Output is correct |
| 7 |
Correct |
19 ms |
39604 KB |
Output is correct |
| 8 |
Correct |
15 ms |
39508 KB |
Output is correct |
| 9 |
Correct |
16 ms |
39508 KB |
Output is correct |
| 10 |
Correct |
25 ms |
42692 KB |
Output is correct |
| 11 |
Correct |
35 ms |
44880 KB |
Output is correct |
| 12 |
Correct |
26 ms |
42696 KB |
Output is correct |
| 13 |
Correct |
137 ms |
65536 KB |
Output is correct |
| 14 |
Correct |
134 ms |
65536 KB |
Output is correct |
| 15 |
Correct |
141 ms |
65536 KB |
Output is correct |
| 16 |
Correct |
155 ms |
65536 KB |
Output is correct |
| 17 |
Correct |
124 ms |
65536 KB |
Output is correct |
| 18 |
Correct |
136 ms |
65536 KB |
Output is correct |
| 19 |
Correct |
136 ms |
65536 KB |
Output is correct |
| 20 |
Correct |
102 ms |
65536 KB |
Output is correct |
