Submission #749296

#	Time	Username	Problem	Language	Result	Execution time	Memory
749296		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]);
    int mx = *max_element(a.begin(), a.end()), y;
    for (int i = n - 1; i >= 0; i--)
        if (a[i] == mx) {
            y = i;
            break;
        }
    vector<int> v;
    for (int i = n - 1; i >= 1; i--) {
        if (i >= y) if (a[i] >= a[i - 1]) v.push_back(i);
        else if (a[i] == mx) v.push_back(i);
        else if (i < y) break;
    }
    reverse(v.begin(), v.end());
    if (v.empty()) {
        cout << "0\n";
    } else {
        long long ans = 0;
        for (int i = 1; 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 (v.size() != 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';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:47:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   47 |         if (i >= y) if (a[i] >= a[i - 1]) v.push_back(i);
      |            ^
Main.cpp:47:9: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |         if (i >= y) if (a[i] >= a[i - 1]) v.push_back(i);
      |         ^~

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