Submission #983807

#	Time	Username	Problem	Language	Result	Execution time	Memory
983807		vjudge1	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	144 ms	8064 KiB

Main

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

#define int long long
#define str string

struct SegTree {

    int size = 1;
    vector<int> adds;

    SegTree (int n){
        while(size < n)
            size <<= 1;
        adds.resize(size << 1);
    }

    void add(int l, int r, int v, int x, int lx, int rx){
        if(l <= lx and rx <= r){
            adds[x] += v;
            return;
        }
        if(rx <= l or r <= lx)
            return;
        int m = (lx + rx) >> 1;
        add(l, r, v, (x << 1) + 1, lx, m);
        add(l, r, v, (x << 1) + 2, m, rx);
    }

    void add(int l, int r, int x){
        add(l, r, x, 0, 0, size);
    }

    int get(int n, int x, int lx, int rx){
        if(lx + 1 == rx)
            return adds[x];
        int mid = (lx + rx) >> 1;
        if(n < mid)
            return get(n, (x << 1) + 1, lx, mid) + adds[x];
        else
            return get(n, (x << 1) + 2, mid, rx) + adds[x];
    }

    int get(int i){
        return get(i, 0, 0, size);
    }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    int left = 0, right = n - 1;
    int ans = 0;
    SegTree s(n);
    for(int i = 0; i < n; i ++)
        s.add(i, i + 1, a[i]);
    while(left < right){
        while(left + 1 < n and s.get(left) < s.get(left + 1))
            left ++;
        while(right - 1 >= 0 and s.get(right - 1) > s.get(right))
            right --;
        if(left < right){
            if(left + 1 == right and s.get(left) == s.get(right)){
                ans ++;
                break;
            }
            int x = s.get(left) - s.get(left + 1) + 1, y = s.get(right) - s.get(right - 1) + 1;
            if(x <= y)
                ans += x, s.add(left + 1, right, x);
            else
                ans += y, s.add(left + 1, right, y);
        }
        else
            break;
    }
    cout << ans;
}

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