Submission #696323

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

Main

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

struct segtree {
    int l, r, mid;
    LL val = 0, lazy = 0;
    segtree *lc, *rc;
    segtree(int L, int R) {
        l = L;
        r = R;
        mid = (l + r) / 2;
        if (l != r) {
            lc = new segtree(l, mid);
            rc = new segtree(mid + 1, r);
        }
    }
    void apply(LL X) {
        // val += X;
        val += X * (r - l + 1);
        lazy += X;
    }
    void push() {
        if (l == r) return;
        lc->apply(lazy);
        rc->apply(lazy);
        lazy = 0;
    }
    void update(int L, int R, LL X) {
        push();
        if (l == L && r == R) {
            apply(X);
            return;
        }
        else if (R <= mid) lc->update(L, R, X);
        else if (L >= mid + 1) rc->update(L, R, X);
        else {
            lc->update(L, mid, X);
            rc->update(mid + 1, R, X);
        }
        // val = min(lc->val, rc->val);
        val = lc->val + rc->val;
    }
    LL query(int L, int R) {
        push();
        if (l == L && r == R) return val;
        else if (R <= mid) return lc->query(L, R);
        else if (L >= mid + 1) return rc->query(L, R);
        else {
            // return min(lc->query(L, mid), rc->query(mid + 1, R));
            return lc->query(L, mid) + rc->query(mid + 1, R);
        }
    }
    //segroot = new segtree(0, n - 1)
} *segroot;

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	long long ans = 0;
	vector<long long> a(n + 1);
	vector<bool> b(n + 1, false);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int l = 2, r = n - 1;
	while (l <= n && a[l] > a[l - 1]) l++;
	while (r >= 1 && a[r] > a[r + 1]) r--;
	if (l > n || r < 1) {
		cout << "0\n";
		return 0;
	}
	segroot = new segtree(0, n + 1);
	for (int i = 1; i <= n; i++) {
		segroot->update(i, i, a[i]);
	}
	while (l <= r) {
		long long L = segroot->query(l, l);
		long long L1 = segroot->query(l-1, l-1);
		long long R = segroot->query(r, r);
		long long R1 = segroot->query(r+1, r+1);
		long long add = min(abs(L - L1), abs(R - R1)) + 1;
		ans += add;
		segroot->update(l, r, add);
		while (l <= n && (segroot->query(l, l)) > (segroot->query(l-1, l-1))) {
			l++;
		}
		while (r >= 1 && (segroot->query(r, r)) > (segroot->query(r+1, r+1))) {
			r--;
		}
	}
	if (l <= n && r >= 1 && a[l] == a[r]) ans++;
	cout << ans << endl;
	return 0;
}

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