Submission #937854

#	Time	Username	Problem	Language	Result	Execution time	Memory
937854		zwezdinv	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	51 ms	4724 KiB

Main

#include <bits/stdc++.h>


struct fenwick {
        int n;
        std::vector<long long> fenw;

        fenwick() = default;
        fenwick(int n) : n(n), fenw(n, 0) {}

        void upd(int k, long long x) {
                for (; k < n; k |= k + 1) fenw[k] += x;
        }

        long long get(int k) {
                long long res = 0;
                for (; k >= 0; k &= k + 1, k--) res += fenw[k];
                return res;
        }

        long long get(int l, int r) {
                return get(r) - get(l - 1);
        }
};

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n;
        std::cin >> n;
        std::vector<int> a(n);
        for (auto& i : a) std::cin >> i;
        fenwick fenw(n + 1);
        for (int i = 0; i < n; ++i) {
                fenw.upd(i, a[i]);
                fenw.upd(i + 1, -a[i]);
        }
        int l = 0, r = n - 1;
        long long ans = 0;
        while (true) {
                while (l + 1 < n && fenw.get(l) < fenw.get(l + 1)) l++;
                while (r - 1 >= 0 && fenw.get(r - 1) > fenw.get(r)) r--;
                if (l == r) break;
                if (l + 1 == r) {
                        if (fenw.get(l) != fenw.get(r)) break;
                        ans++;
                        break;
                }
                long long d = std::min(fenw.get(r) - fenw.get(r - 1), fenw.get(l) - fenw.get(l + 1)) + 1;
                ans += d;
                fenw.upd(l + 1, d);
                fenw.upd(r, -d);
        }
        std::cout << ans << '\n';
}

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60