Submission #757732

#	Time	Username	Problem	Language	Result	Execution time	Memory
757732		happypotato	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	0 / 100	1 ms	212 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
int32_t main() {
    int n;
    cin >> n;
    int a[n + 1], ps[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    int q;
    cin >> q;
    while (q--) {
        int x, y, l, r;
        cin >> x >> y >> l >> r;
        a[x] = y;
        ps[0] = 0;
        for (int i = 1; i <= n; i++) {
            ps[i] = ps[i - 1] + a[i];
        }
        pii dp[n + 1][2];
        dp[l - 1][0] = {0, 1e18};
        dp[l][0] = {1, a[l]};
        dp[l][1] = {1, -1};
        for (int i = l + 1; i <= r; i++) {
            int ptr = i - 1;
            while (dp[ptr][0].ss <= a[i]) ptr--;
            dp[i][1] = {dp[ptr][0].ff + 1, -1};
            ptr = i - 1;
            dp[i][0] = dp[i - 1][0];
            while (dp[ptr][0].ff == dp[i][0].ff) {
                dp[i][0].ss = dp[ptr][0].ss;
                ptr--;
            }
            dp[i][0].ss += a[i];
        }
        cout << max(dp[r][0].ff, dp[r][1].ff) << endl;
    }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11