oj.uz

Submission #757732

# Submission time Handle Problem Language Result Execution time Memory
757732 2023-06-13T16:39:46 Z happypotato Mizuyokan 2 (JOI23_mizuyokan2) C++17
0 / 100
 1 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -