oj.uz

Submission #932712

# Submission time Handle Problem Language Result Execution time Memory
932712 2024-02-24T04:20:01 Z ShadowShark Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 352 ms 28892 KB 
#include <bits/stdc++.h>
using namespace std;

   ///***Author: ShadowShark***\\\
Con thuyen nho vuot muon trung nui non

const int maxN = 2e5 + 5;
long long a[maxN];
int n, q;

namespace subtask2 {

long long d[maxN], dp[maxN][2];

void solve() {
    for (int i = 1; i <= q; i++) {
        int l, r, x;
        cin >> l >> r >> x;

        for (int i = l; i <= r; i++)
            a[i] += x;

        for (int i = 1; i < n; i++)
            d[i] = a[i] - a[i + 1];

        d[n] = 0; dp[0][0] = 0; dp[0][1] = 0;

        for (int i = 1; i < n ; i++){
            dp[i][0]= max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1]= max(dp[i - 1][0], dp[i - 1][1] * (d[i] * d[i - 1] >= 0)) + abs(d[i]);
        }

        cout << max(dp[n - 1][0], dp[n - 1][1]) << '\n';
    }
}
}

namespace subtask3 {
    const long long inf = 1e18;
    long long d[maxN];

    struct node {
        long long f[2][2]; /// dp [left chosen?][right chosen?]
    } st[4 * maxN];

    node merge_node(node a, node b, int mid) {
        node temp = {-inf, -inf, -inf, -inf};

        /// Case d[mid] and d[mid + 1] are diff comp to 0
        temp.f[1][1] = max(a.f[1][1] + b.f[0][1], a.f[1][0] + b.f[1][1]);
        temp.f[1][0] = max(a.f[1][1] + b.f[0][0], a.f[1][0] + b.f[1][0]);
        temp.f[0][1] = max(a.f[0][0] + b.f[1][1], a.f[0][1] + b.f[0][1]);
        temp.f[0][0] = max(a.f[0][1] + b.f[0][0], a.f[0][0] + b.f[1][0]);

        /// Case not
        if (!(d[mid] * d[mid + 1] < 0)) {
            temp.f[1][1] = max(a.f[1][1], a.f[1][0]) + max(b.f[1][1], b.f[0][1]);
            temp.f[1][0] = max(a.f[1][1], a.f[1][0]) + max(b.f[1][0], b.f[0][0]);
            temp.f[0][1] = max(a.f[0][1], a.f[0][0]) + max(b.f[0][1], b.f[1][1]);
            temp.f[0][0] = max(a.f[0][1], a.f[0][0]) + max(b.f[0][0], b.f[1][0]);
        }

        return temp;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            st[id].f[1][1] = abs(d[l]);
            st[id].f[0][0] = st[id].f[0][1] = st[id].f[1][0] = -inf;
            return ;
        }

        int mid = (l + r) / 2;

        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);

        st[id] = merge_node(st[2 * id], st[2 * id + 1], mid);
        return ;
    }

    void update(int id, int l, int r, int pos) {
        if (pos < l || r < pos) return ;

        if (l == r) {
            st[id].f[1][1] = abs(d[pos]);
            st[id].f[0][0] = st[id].f[0][1] = st[id].f[1][0] = -inf;
            return ;
        }

        int mid = (l + r) / 2;
        update(2 * id, l, mid, pos);
        update(2 * id + 1, mid + 1, r, pos);

        st[id] = merge_node(st[2 * id], st[2 * id + 1], mid);
        return ;
    }

    void solve() {
        for (int i = 1; i < n; i++)
            d[i] = a[i] - a[i + 1];

        build(1, 1, n - 1);

        for (int i = 1; i <= q; i++) {
            int l, r, x;
            cin >> l >> r >> x;

            if (l > 1) {
                d[l - 1] -= x;
                update(1, 1, n - 1, l - 1);
            }

            d[r] += x;
            update(1, 1, n - 1, r);

            cout << max({st[1].f[0][0], st[1].f[0][1], st[1].f[1][0], st[1].f[1][1]}) << '\n';
        }
    }

}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("sjeckanje.inp", "r", stdin);
   // freopen("sjeckanje.out", "w", stdout);

    cin >> n >> q;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    if (n <= 3000) subtask2::solve();
        else subtask3::solve();

    return 0;
}

Compilation message

Main.cpp:4:4: warning: multi-line comment [-Wcomment]
    4 |    ///***Author: ShadowShark***\\\
      |    ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 37 ms 4600 KB Output is correct
8 Correct 39 ms 4444 KB Output is correct
9 Correct 37 ms 4444 KB Output is correct
10 Correct 37 ms 4620 KB Output is correct
11 Correct 38 ms 4624 KB Output is correct
12 Correct 37 ms 4856 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 37 ms 4600 KB Output is correct
8 Correct 39 ms 4444 KB Output is correct
9 Correct 37 ms 4444 KB Output is correct
10 Correct 37 ms 4620 KB Output is correct
11 Correct 38 ms 4624 KB Output is correct
12 Correct 37 ms 4856 KB Output is correct
13 Incorrect 352 ms 28892 KB Output isn't correct
14 Halted 0 ms 0 KB -