oj.uz

Submission #541873

# Submission time Handle Problem Language Result Execution time Memory
541873 2022-03-24T17:59:22 Z AlperenT Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 544 ms 32024 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

long long n, q, arr[N], l, r, x;

struct SegNode{
    int l, r;
    long long OO, OX, XO, XX;
};

struct SegTree{
    SegNode tree[N * 4];

    SegNode merge(SegNode a, SegNode b){
        SegNode c = {a.l, b.r, 0, 0, 0, 0};

        // OO

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.OO = a.OO + b.OO - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.OO = a.OO + b.OO;

        c.OO = max({c.OO, a.OO + b.XO, a.OX + b.OO, a.OX + b.XO});

        // OX

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.OX = a.OO + b.OX - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.OX = a.OO + b.OX;

        c.OX = max({c.OX, a.OO + b.XX, a.OX + b.OX, a.OX + b.XX});

        // XO

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.XO = a.XO + b.OO - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.XO = a.XO + b.OO;

        c.XO = max({c.XO, a.XO + b.XO, a.XX + b.OO, a.XX + b.XO});

        // XX

        if(max(arr[a.r], arr[b.l]) > 0 && min(arr[a.r], arr[b.l]) < 0){
            c.XX = a.XO + b.OX - min(abs(arr[a.r]), abs(arr[b.l]));
        }
        else c.XX = a.XO + b.OX;

        c.XX = max({c.XX, a.XO + b.XX, a.XX + b.OX, a.XX + b.XX});

        return c;
    }

    void build(int v = 1, int l = 1, int r = n - 1){
        if(l > r) return;
        else if(l == r) tree[v] = {l, l, abs(arr[l]), 0, 0, 0};
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m); build(v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    void update(int pos, long long val, int v = 1, int l = 1, int r = n - 1){
        if(l > r) return;
        else if(l == r){
            arr[l] += val;
            tree[v].OO = abs(arr[l]);
        }
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, val, v * 2, l, m);
            else update(pos, val, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    long long getans(){
        return max({tree[1].OO, tree[1].OX, tree[1].XO, tree[1].XX});
    }
};

SegTree sgt;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> q;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    for(int i = 1; i <= n - 1; i++) arr[i] = arr[i + 1] - arr[i];

    sgt.build();

    while(q--){
        cin >> l >> r >> x;

        if(l - 1 >= 1) sgt.update(l - 1, x);
        if(r <= n - 1) sgt.update(r, -x);

        cout << sgt.getans() << "\n";
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 5 ms 808 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 5 ms 808 KB Output is correct
13 Correct 527 ms 31544 KB Output is correct
14 Correct 522 ms 31468 KB Output is correct
15 Correct 542 ms 31412 KB Output is correct
16 Correct 544 ms 31392 KB Output is correct
17 Correct 529 ms 31380 KB Output is correct
18 Correct 522 ms 32024 KB Output is correct