Submission #487862

#	Time	Username	Problem	Language	Result	Execution time	Memory
487862		Victor	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	656 ms	29912 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

ll diffs[200001];

struct Node {
    int lo, hi;
    ll best, skipL, skipR, skipBoth;
    Node *l, *r;
    Node(int L, int R) : lo(L), hi(R) {
        if (lo == hi)return;

        else if (hi - lo == 1) {
            best = abs(diffs[lo]);
            skipL = 0;
            skipR = 0;
            skipBoth = 0;

        } else {
            int mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
            combine();
        }
    }

    void update(int pos, ll val) {
        if (pos < lo || hi <= pos) return;
        if (hi - lo == 1) {
            best = abs(val);
            // debug(best);
            return;
        }

        l->update(pos, val);
        r->update(pos, val);
        combine();
    }

    void combine() {
        if (diffs[l->hi - 1] * diffs[r->lo] >= 0) {
            best = l->best + r->best;
            skipL = l->skipL + r->best;
            skipR = l->best + r->skipR;
            skipBoth = l->skipL + r->skipR;

        } else {
            best = max(l->skipR + r->best, l->best + r->skipL);
            skipL = max(l->skipL + r->skipL, l->skipBoth + r->best);
            skipR = max(l->skipR + r->skipR, l->best + r->skipBoth);
            skipBoth = max(l->skipL + r->skipBoth, l->skipBoth + r->skipR);
        }
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, q;
    ll prev;
    cin >> n >> q >> prev;
    diffs[n - 1] = 0;
    rep(i, 0, n - 1) {
        ll num;
        cin >> num;
        diffs[i] = num - prev;
        prev = num;
    }

    Node segtree(0, n - 1);
    //cout << segtree.best << endl;

    while (q--) {
        int lo, hi;
        ll val;
        cin >> lo >> hi >> val;

        if (n != 1) {
            --lo;
            --hi;

            if (lo) diffs[--lo] += val;

            if (hi != n - 1)
                diffs[hi] -= val;
            else
                --hi;

            segtree.update(lo, diffs[lo]);
            segtree.update(hi, diffs[hi]);
        }

        // rep(i,0,n-1)cout<<diffs[i]<<' ';
        // cout<<endl;
        cout<<segtree.best<<endl;
    }
    return 0;
}

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