제출 #876039

#제출 시각아이디문제언어결과실행 시간메모리
876039The_Samurai등산 경로 (IZhO12_route)C++17
0 / 100
145 ms65536 KiB
// 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(3 * n), right(3 * n); stack<int> s; for (int i = 0; i < 3 * n; i++) { while (!s.empty() and a[s.top()] <= a[i]) s.pop(); left[i] = 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(); right[i] = s.empty() ? 3 * n : s.top(); s.push(i); } 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] == -1 and right[i] == 3 * n) break; int next = sg.get(sg.get_sum(0, left[i]) + 1); while (next != -1 and next < right[i]) { upd(next); next = sg.get(sg.get_sum(0, left[i]) + 1); } x = min(left[i] == -1 ? inf : a[left[i]], right[i] == 3 * n ? inf : a[right[i]]); val.emplace_back(1ll * (right[i] - left[i] - 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 timeMemoryGrader output
Fetching results...