Submission #426758

#	Time	Username	Problem	Language	Result	Execution time	Memory
426758		tengiz05	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	86 ms	3448 KiB

Main

#include <bits/stdc++.h>
using i64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<i64> t(2 * n);
    for (int i = 0; i < n; i++) {
        std::cin >> t[i + n];
    }
    i64 ans = 0;
    auto update = [&](int l, int r, i64 val) {
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l % 2 == 1) t[l++] += val;
            if (r % 2 == 0) t[r--] += val;
        }
    };
    auto a = [&](int p) {
        i64 res = 0;
        for (p += n; p > 0; p >>= 1) {
            res += t[p];
        }
        return res;
    };
    for (int l = 1, r = n - 1; l <= r; ) {
        while (l < n && a(l) > a(l - 1)) l++;
        while (r - 1 >= 0 && a(r - 1) > a(r)) r--;
        if (l == r) {
            ans++;
            break;
        }
        if (l > r) break;
        i64 val = std::min(a(l - 1) + 1 - a(l), a(r) + 1 - a(r - 1));
        update(l, r - 1, val);
        ans += val;
    }
    std::cout << ans << "\n";
    return 0;
}

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