oj.uz

Submission #932709

# Submission time Handle Problem Language Result Execution time Memory
932709 2024-02-24T04:19:14 Z ShadowShark Sjeckanje (COCI21_sjeckanje) C++17
15 / 110
 4 ms 4700 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 <= 1000) 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 4444 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 4440 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4440 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 4 ms 4700 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4440 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 4 ms 4700 KB Output isn't correct
8 Halted 0 ms 0 KB -