Submission #861744

#	Time	Username	Problem	Language	Result	Execution time	Memory
861744		dbence	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	332 ms	39956 KiB

Main

#include <bits/stdc++.h>
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
using namespace std;
typedef long long ll;
const ll N = 2e5 + 1;
ll n, q, current, arr[N], dif[N], dp[N];

bool difsign(ll x, ll y) {
    return (x >= 0) != (y >= 0);
}

struct Node {
    ll l, r;
    ll pre, ans, suf, ins;

    Node operator + (const Node &node) const {
        Node result;
        result.l = l;
        result.r = node.r;
        result.ans = result.pre = result.suf = result.ins = 0;
        result.ans = max(result.ans, pre + node.ans);
        result.ans = max(result.ans, ans + node.suf);
        result.pre = max(result.pre, ans + node.ins);
        result.pre = max(result.pre, pre + node.pre);
        result.suf = max(result.suf, ins + node.ans);
        result.suf = max(result.suf, suf + node.suf);
        result.ins = max(result.ins, suf + node.ins);
        result.ins = max(result.ins, ins + node.pre);
        if (!difsign(dif[r], dif[node.l])) {
            result.ans = max(result.ans, ans + node.ans);
            result.pre = max(result.pre, ans + node.pre);
            result.suf = max(result.suf, suf + node.ans);
            result.ins = max(result.ins, suf + node.pre);
        }
        return result;
    }
} node[N << 2];

void merge(ll id, ll l, ll r) {
    node[id] = node[l] + node[r];
}

void init(ll id) {
    node[id].ans = abs(dif[node[id].l]);
    node[id].pre = 0;
    node[id].suf = 0;
    node[id].ins = 0;
}

void build(ll id, ll l, ll r) {
    node[id].l = l;
    node[id].r = r;
    if (l == r) {
        init(id);
        return;
    }
    ll q = l + r >> 1;
    build(l(id), l, q);
    build(r(id), q + 1, r);
    merge(id, l(id), r(id));
}

void update(ll id, ll i, ll x) {
    if (node[id].l == node[id].r) {
        dif[i] += x;
        init(id);
        return;
    }
    ll q = node[id].l + node[id].r >> 1;
    if (i <= q) {
        update(l(id), i, x);
    } else {
        update(r(id), i, x);
    }
    merge(id, l(id), r(id));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    for (ll i = 1; i < n; ++i) {
        dif[i] = arr[i + 1] - arr[i];
    }
    build(0, 1, n - 1);
    for (ll i = 0; i < q; ++i) {
        ll l, r, x;
        cin >> l >> r >> x;
        
        if (l > 1)
            update(0, l - 1, x);
        if (r < n)
            update(0, r, -x);
        
        cout << node[0].ans << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'void build(ll, ll, ll)':
Main.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     ll q = l + r >> 1;
      |            ~~^~~
Main.cpp: In function 'void update(ll, ll, ll)':
Main.cpp:70:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     ll q = node[id].l + node[id].r >> 1;
      |            ~~~~~~~~~~~^~~~~~~~~~~~

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