Submission #749302

#	Time	Username	Problem	Language	Result	Execution time	Memory
749302		Desh03	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	0 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]);\
    long long ans = 0;
    for (int i = 1, j = n - 1; ; i++) {
        long long a = fen.qry(i - 1), b = fen.qry(i);
        while (j && fen.qry(j - 1) > fen.qry(j)) --j;
        if (j < i) break;
        if (a >= b) {
            if (i ^ j) fen.upd(i, j - 1, a - b + 1);
            ans += a - b + 1;
        }
    }
    cout << ans << '\n';
}

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