// 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 < 3 * 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 >= 0; 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(3 * 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;
auto upd = [&](int i) {
for (int j = i - 2 * n; j <= i + 2 * n; j += n) {
if (j < 0 or j >= 3 * n) continue;
sg.set(j, 0);
}
};
for (auto [x, i]: v) {
if (!sg.get_sum(i, i)) continue;
if (left[i - n] == -1 and right[i - n] == 3 * n) break;
int next = sg.get(sg.get_sum(0, left[i - n]) + 1);
while (next != -1 and next < right[i - n]) {
upd(next);
next = sg.get(sg.get_sum(0, left[i - n]) + 1);
}
x = min(left[i - n] == -1 ? inf : a[left[i - n]], right[i - n] == 3 * n ? inf : a[right[i - n]]);
val.emplace_back(1ll * (right[i - n] - left[i - n] - 1), x - a[i]);
}
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 |
1 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 |
0 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 |
1 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 |
79 ms |
9192 KB |
Output is correct |
| 11 |
Correct |
142 ms |
8680 KB |
Output is correct |
| 12 |
Correct |
83 ms |
8136 KB |
Output is correct |
| 13 |
Runtime error |
398 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Halted |
0 ms |
0 KB |
- |
