Submission #1163809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163809		CodeLakVN	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	452 ms	32916 KiB

Main

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

#define task "SJECKANJE"
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define ll long long

const int N = (int)2e5 + 5;
const ll INF = (ll)1e18 + 1408;

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }

int n, q;
int a[N];

struct NODE {
    ll head, tail;
    ll dp[2][2]; // The first dimension shows the number that will be inserted before the segment (if the head of the segment is a, and x is the number that will be inserted if x < a then the first dimension will be 0, and 1 if x > a), similar for the second dimension
};

struct IT {
    NODE tree[4 * N];
    ll lazy[4 * N];

    void down(int id) {
        if (lazy[id] == 0) return;
        ll val = lazy[id];
        tree[2 * id].head += val;
        tree[2 * id].tail += val;
        lazy[2 * id] += val;
        tree[2 * id + 1].head += val;
        tree[2 * id + 1].tail += val;
        lazy[2 * id + 1] += val;
        lazy[id] = 0;
    }

    NODE combine(NODE a, NODE b) {
        NODE res;
        res.head = a.head, res.tail = b.tail;
        FOR(i, 0, 1) FOR(j, 0, 1) res.dp[i][j] = -INF;
        FOR(leftHead, 0, 1) FOR(leftTail, 0, 1) {
            if (a.dp[leftHead][leftTail] == -INF) continue;
            FOR(rightHead, 0, 1) FOR(rightTail, 0, 1) {
                if (b.dp[rightHead][rightTail] == -INF) continue;
                maximize(res.dp[leftHead][rightTail], a.dp[leftHead][leftTail] + b.dp[rightHead][rightTail]);
                if (a.tail < b.head && leftTail == 1 && leftTail != rightHead)
                    maximize(res.dp[leftHead][rightTail], a.dp[leftHead][leftTail] + b.dp[rightHead][rightTail] + b.head - a.tail);
                if (a.tail > b.head && leftTail == 0 && leftTail != rightHead)
                    maximize(res.dp[leftHead][rightTail], a.dp[leftHead][leftTail] + b.dp[rightHead][rightTail] + a.tail - b.head);
            }
        }
        return res;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            tree[id].dp[1][1] = tree[id].dp[0][0] = -INF;
            tree[id].dp[0][1] = tree[id].dp[1][0] = 0;
            tree[id].head = tree[id].tail = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        tree[id] = combine(tree[2 * id], tree[2 * id + 1]);
        // cout << "ID: " << id << "\n";
        // cout << "head: " << tree[id].head << ", tail: " << tree[id].tail << "\n";
        // cout << "0 0: " << tree[id].dp[0][0] << "\n";
        // cout << "0 1: " << tree[id].dp[0][1] << "\n";
        // cout << "1 0: " << tree[id].dp[1][0] << "\n";
        // cout << "1 1: " << tree[id].dp[1][1] << "\n";
    }

    void update(int id, int l, int r, int u, int v, ll val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            // cout << "ID: " << id << ": CHANGED!!!!\n";
            // cout << tree[id].head << "\n";
            tree[id].head += val;
            tree[id].tail += val;
            lazy[id] += val;
            // cout << "head: " << tree[id].head << ", tail: " << tree[id].tail << "\n";
            // cout << "lazy: " << lazy[id] << "\n";
            return;
        }
        // cout << "ID: " << id << " lazy: " << lazy[id] << "\n";
        down(id);
        int mid = (l + r) >> 1;
        update(2 * id, l, mid, u, v, val);
        update(2 * id + 1, mid + 1, r, u, v, val);
        tree[id] = combine(tree[2 * id], tree[2 * id + 1]);
        // cout << "ID: " << id << "\n";
        // cout << "head: " << tree[id].head << ", tail: " << tree[id].tail << "\n";
        // cout << "0 0: " << tree[id].dp[0][0] << "\n";
        // cout << "0 1: " << tree[id].dp[0][1] << "\n";
        // cout << "1 0: " << tree[id].dp[1][0] << "\n";
        // cout << "1 1: " << tree[id].dp[1][1] << "\n";
    }

    ll getMax(int id) {
        return max(max(tree[id].dp[0][0], tree[id].dp[0][1]), max(tree[id].dp[1][0], tree[id].dp[1][1]));
    }
} segtree;

int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];

    segtree.build(1, 1, n);

    while (q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        segtree.update(1, 1, n, l, r, x);
        cout << segtree.getMax(1) << "\n";
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55