Submission #639455

#	Time	Username	Problem	Language	Result	Execution time	Memory
639455		vbee	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1217 ms	47688 KiB

Main

#include <bits/stdc++.h>
#define TASK ""
#define ll long long
#define fi first
#define se second
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define ii pair<int, int>
#define vi vector<int>

using namespace std;

const int oo = 1e9 + 7;
const int mod = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 2e5 + 7;

bool maximize(ll &a, ll b){
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
struct Node{
    ll border[2] = {};
    ll value[2][2] = {};
    Node(){}
    Node (ll val){
        border[0] = border[1] = val;
        value[0][0] = 0;
        value[0][1] = value[1][0] = -loo;
        value[1][1] = abs(val);
    }

    Node combine(const Node &other) const {
        Node ret;
        ret.border[0] = border[0];
        ret.border[1] = other.border[1];
        for (int l = 0; l < 2; l++){
            for (int m = 0; m < 2; m++){
                for (int o = 0; o < 2; o++){
                    for (int r = 0; r < 2; r++){
                        if (o && m){
                            if ((border[1] < 0) == (other.border[0] < 0)){
                                maximize(ret.value[l][r], value[l][m] + other.value[o][r]);
                            }
                        }
                        else maximize(ret.value[l][r], value[l][m] + other.value[o][r]);
                    }
                }
            }
        }
        return ret;
    }

};

struct ST{
    vector<Node> t;
    void init(int n){
        t.resize(n * 4 + 7);
    }
    void update(int v, int lt, int rt, int pos, ll value){
        if (lt == rt){
            t[v].border[0] += value;
            t[v].border[1] += value;
            t[v].value[1][1] = abs(t[v].border[0]);
            return;
        }
        int middle = (rt + lt) / 2;
        if (pos <= middle) update(v * 2, lt, middle, pos, value);
        else update(v * 2 + 1, middle + 1, rt, pos, value);
        t[v] = t[v * 2].combine(t[v * 2 + 1]);
    }
    Node getmax(int v, int lt, int rt, int l, int r){
        if (l > r) return Node(0);
        if (lt == l && rt == r) return t[v];
        int middle = (rt + lt) / 2;
        Node temp = getmax(v * 2, lt, middle, l, min(middle, r));
        return temp.combine(getmax(v * 2 + 1, middle + 1, rt, max(middle + 1, l), r));
    }
};

ll n, q;

int main(){
    ios_base::sync_with_stdio(0); cin.tie();
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);
    cin >> n >> q;
    ST seg;
    seg.init(n - 1);
    int pre = 0;
    cin >> pre;
    for (int i = 1; i < n; i++){
        int x; cin >> x;
        seg.update(1, 1, n - 1, i, x - pre);
        pre = x;
    }
    while (q--){
        int l, r, x; cin >> l >> r >> x;
        if (l > 1) seg.update(1, 1, n - 1, l - 1, x);
        if (r < n) seg.update(1, 1, n - 1, r, -x);
        cout << seg.getmax(1, 1, n - 1, 1, n - 1).value[1][1] << "\n";
    }
    return 0;
}

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