Submission #749285

#	Time	Username	Problem	Language	Result	Execution time	Memory
749285		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]);
    int mx = *max_element(a.begin(), a.end()), y;
    for (int i = n - 1; i >= 0; i--)
        if (a[i] == mx) {
            y = i;
            break;
        }
    int p = y;
    while (p && a[p - 1] == mx) --p;
    long long ans = 0;
    for (int i = 1; i < y; i++) {
        long long a = fen.qry(i - 1), b = fen.qry(i);
        if (a >= b) {
            fen.upd(i, y - 1, a - b + 1), ans += a - b + 1;
            if (y ^ p) --y;
        }
    }
    if (y && fen.qry(y - 1) == fen.qry(y)) ++ans;
    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:55:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     if (y && fen.qry(y - 1) == fen.qry(y)) ++ans;
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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