Submission #749299

#	Time	Username	Problem	Language	Result	Execution time	Memory
749299		Desh03	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	1 ms	212 KiB

Main

#include <bits/stdc++.h>
using namespace std;

template <typename T>
    struct fenwick {
        vector<T> fen;
        int n;
        fenwick(int n_) : n(n_) {
            fen.resize(n);
        }
        void upd(int x, T d) {
            while (x < n) {
                fen[x] += d;
                x |= x + 1;
            }
        }
        T qry(int x) {
            T s = 0;
            while (x >= 0) {
                s += fen[x];
                x = (x & (x + 1)) - 1;
            }
            return s;
        }
        void upd(int l, int r, T d) {
            upd(l, d);
            upd(r + 1, -d);
        }
    };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    fenwick<long long> fen(n);
    for (int i = 0; i < n; i++) cin >> a[i], fen.upd(i, i, a[i]);
    vector<int> v;
    for (int i = n - 1; i >= 1; i--) if (a[i] >= a[i - 1]) v.push_back(i);
    if (v.empty()) {
        cout << "0\n";
    } else {
        reverse(v.begin(), v.end());
        long long ans = 0;
        for (int i = 1; v.size() && i < v.back(); i++) {
            long long a = fen.qry(i - 1), b = fen.qry(i);
            if (a >= b) {
                fen.upd(i, v.back() - 1, a - b + 1), ans += a - b + 1;
                if (fen.qry(v.back()) < fen.qry(v.back() - 1)) v.pop_back();
            }
        }
        if (v.size() && fen.qry(v.back() - 1) == fen.qry(v.back())) ++ans;
        cout << ans << '\n';
    }
}

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