Submission #566247

#	Time	Username	Problem	Language	Result	Execution time	Memory
566247		Tam_theguide	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	720 ms	29604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
int n , q; ll a[200005], d[200005];
struct node{
    ll a[2][2];
    void init(){
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                a[i][j] = -INF;
            }
        }
    }

};
node seg[800005];
void push(int root, int tl, int tr){
    int tm = (tl + tr) / 2; node c1 = seg[2 * root], c2 = seg[2 * root + 1];
    ll tmp[2][2];
    for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j ++) tmp[i][j] = -1e18;
    for (int i = 0; i <= 1; i++){
        for (int j = 0; j <= 1; j++){
            for (int t = 0; t <= 1; t++){
                for (int k = 0; k <= 1; k++){
                    if (c1.a[i][j] != -INF && c2.a[t][k] != -INF){

                        if (j == 1 && t == 1 && d[tm] * d[tm + 1] < 0) continue;

                        tmp[i][k] = max(tmp[i][k], c1.a[i][j] + c2.a[t][k]);
                    }
                }
            }
        }
    }
    for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1;j ++) seg[root].a[i][j] = tmp[i][j];
}
void buildtree(int root, int tl, int tr){
    if (tl == tr){
        seg[root].init();
        seg[root].a[1][1] = abs(d[tl]);
        seg[root].a[0][0] = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    buildtree(2 * root, tl, tm);
    buildtree(2 * root + 1, tm + 1, tr);
    push(root, tl, tr);
}
void update(int root, int tl, int tr, int pos){
    if (tl == tr){
        seg[root].init();
        seg[root].a[1][1] = abs(d[tl]);
        seg[root].a[0][0] = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * root, tl, tm, pos);
    else update(2 * root + 1, tm + 1, tr, pos);
    push(root, tl, tr);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q; for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i < n;i++) d[i] = a[i] - a[i + 1];
    //for (int i = 0; i <= 4 * n; i++) seg[i].init();
    //cout << seg[1].a[0][1] + INF;
    buildtree(1, 1, n - 1);
    while (q--){
        int l, r; ll x; cin >> l >> r >> x;
        d[l - 1] -= x; d[r] += x;
        update(1, 1, n - 1, l - 1); update(1, 1, n - 1, r);
        cout << max({seg[1].a[0][0], seg[1].a[0][1], seg[1].a[1][1], seg[1].a[1][0]}) << '\n';
    }
}

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