oj.uz

Submission #487862

# Submission time Handle Problem Language Result Execution time Memory
487862 2021-11-16T20:37:05 Z Victor Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 656 ms 29912 KB 
#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.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 6 ms 660 KB Output is correct
9 Correct 8 ms 844 KB Output is correct
10 Correct 7 ms 716 KB Output is correct
11 Correct 6 ms 716 KB Output is correct
12 Correct 6 ms 756 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 6 ms 660 KB Output is correct
9 Correct 8 ms 844 KB Output is correct
10 Correct 7 ms 716 KB Output is correct
11 Correct 6 ms 716 KB Output is correct
12 Correct 6 ms 756 KB Output is correct
13 Correct 626 ms 29684 KB Output is correct
14 Correct 628 ms 29844 KB Output is correct
15 Correct 656 ms 29848 KB Output is correct
16 Correct 653 ms 29912 KB Output is correct
17 Correct 623 ms 29836 KB Output is correct
18 Correct 652 ms 29840 KB Output is correct