// I stand with PALESTINE
//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
struct segtree {
vector<int> tree;
int size;
void init(int n) {
size = 1;
while (size < n) size *= 2;
tree.assign(2 * size - 1, 0);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x] = v;
return;
}
int m = (lx + rx) >> 1;
if (i < m) set(i, v, 2 * x + 1, lx, m);
else set(i, v, 2 * x + 2, m, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int get_sum(int l, int r, int x, int lx, int rx) {
if (l >= rx or lx >= r) return 0;
if (l <= lx and rx <= r) return tree[x];
int m = (lx + rx) >> 1;
return get_sum(l, r, 2 * x + 1, lx, m) + get_sum(l, r, 2 * x + 2, m, rx);
}
int get_sum(int l, int r) {
return get_sum(l, r + 1, 0, 0, size);
}
int get(int v, int x, int lx, int rx) {
if (rx - lx == 1) return tree[x] ? lx : -1;
int m = (lx + rx) >> 1;
if (tree[2 * x + 1] >= v) return get(v, 2 * x + 1, lx, m);
else return get(v - tree[2 * x + 1], 2 * x + 2, m, rx);
}
int get(int v) {
return get(v, 0, 0, size);
}
};
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(3 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[2 * n + i] = a[n + i] = a[i];
}
vector<int> left(n), right(n);
stack<int> s;
for (int i = 0; i < 2 * n; i++) {
while (!s.empty() and a[s.top()] <= a[i]) s.pop();
if (n <= i and i < 2 * n) left[i - n] = s.empty() ? -1 : s.top();
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = 3 * n - 1; i >= n; i--) {
while (!s.empty() and a[s.top()] <= a[i]) s.pop();
if (n <= i and i < 2 * n) right[i - n] = s.empty() ? 3 * n : s.top();
s.push(i);
}
while (!s.empty()) s.pop();
segtree sg; sg.init(n);
vector<pair<int, int>> v;
for (int i = 0; i < 3 * n; i++) sg.set(i, 1);
for (int i = n; i < 2 * n; i++) v.emplace_back(a[i], i);
sort(v.begin(), v.end());
vector<pair<int, int>> val;
for (auto [x, i]: v) {
if (!sg.get_sum(i - n, i - n)) continue;
if (left[i - n] == -1 and right[i - n] == 3 * n) break;
int dist, mn;
if (left[i - n] < n) {
right[i - n] %= n;
int next = sg.get(sg.get_sum(0, left[i - n]) + 1);
while (next != -1) {
sg.set(next, 0);
next = sg.get(sg.get_sum(0, left[i - n]) + 1);
}
next = sg.get(1);
while (next != -1 and next < right[i - n]) {
sg.set(next, 0);
next = sg.get(1);
}
dist = (n - left[i - n] - 1) + right[i - n];
} else if (right[i - n] >= 2 * n) {
left[i - n] %= n; right[i - n] %= n;
int next = sg.get(1);
while (next != -1 and next < right[i - n]) {
sg.set(next, 0);
next = sg.get(1);
}
next = sg.get(sg.get_sum(0, left[i - n]) + 1);
while (next != -1) {
sg.set(next, 0);
next = sg.get(sg.get_sum(0, left[i - n]) + 1);
}
dist = right[i - n] + (n - left[i - n] - 1);
} else {
left[i - n] %= n; right[i - n] %= n;
int next = sg.get(sg.get_sum(0, left[i - n]) + 1);
while (next != -1 and next < right[i - n]) {
sg.set(next, 0);
next = sg.get(sg.get_sum(0, left[i - n]) + 1);
}
dist = right[i - n] - left[i - n] - 1;
}
mn = min(a[left[i - n] % n], a[right[i - n] % n]);
val.emplace_back(dist, mn - a[i - n]);
}
sort(val.begin(), val.end());
int ans = 0;
for (auto [cost, cnt]: val) {
if (1ll * cost * cnt <= k) {
ans += cnt;
k -= cost * cnt;
} else {
ans += k / cost;
break;
}
}
cout << ans * 2;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int q = 1;
// cin >> q;
while (q--) {
solve();
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
64 ms |
5912 KB |
Output is correct |
| 11 |
Correct |
118 ms |
5624 KB |
Output is correct |
| 12 |
Correct |
59 ms |
4972 KB |
Output is correct |
| 13 |
Correct |
636 ms |
63656 KB |
Output is correct |
| 14 |
Correct |
649 ms |
63812 KB |
Output is correct |
| 15 |
Correct |
629 ms |
61672 KB |
Output is correct |
| 16 |
Correct |
637 ms |
62868 KB |
Output is correct |
| 17 |
Correct |
684 ms |
62536 KB |
Output is correct |
| 18 |
Correct |
645 ms |
63560 KB |
Output is correct |
| 19 |
Correct |
634 ms |
63576 KB |
Output is correct |
| 20 |
Correct |
572 ms |
50928 KB |
Output is correct |
