Submission #1011945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011945		fryingduc	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	229 ms	50768 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)          
#endif

#define int long long


const int maxn = 2e5+5;
int n, a[maxn], q, d[maxn];

namespace sub12{
    const int N = 3005;
    int f[N][2];
    void compute(){
        d[0] = d[n] = 0;
        for(int i = 1; i <= n; ++i){
            if(d[i] * d[i - 1] < 0){
                f[i][0] = max(f[i - 1][1], f[i - 1][0]);
                f[i][1] = max(f[i - 1][0], f[i - 1][1] - abs(d[i - 1])) + abs(d[i]);
            }
            else{
                f[i][0] = max(f[i - 1][0], f[i - 1][1]);
                f[i][1] = max(f[i - 1][0], f[i - 1][1]) + abs(d[i]);
            }
//            debug(i, f[i][0], f[i][1]);
        }
    }
    void solve(){
        while(q--){
            int l, r, x; cin >> l >> r >> x;
            d[l - 1] -= x;
            d[r] += x;
            compute();
            cout << max(f[n][0], f[n][1]) << '\n';
        }
    }
}
namespace sub3{
    struct Node{
        int f[4], head, tail;
        Node() {
            f[0] = f[1] = f[2] = f[3];
        }
        Node (int x, int y, int z, int t, int head, int tail) : head(head), tail(tail) {
            f[0] = x, f[1] = y, f[2] = z, f[3] = t;
        }
        friend Node operator + (const Node &a, const Node &b){
            Node res;
            if(a.tail * b.head < 0){
                res.f[0] = max(a.f[2] + b.f[0], a.f[0] + b.f[1]);
                res.f[1] = max(a.f[1] + b.f[1], a.f[3] + b.f[0]);
                res.f[2] = max(a.f[0] + b.f[3], a.f[2] + b.f[2]);
                res.f[3] = max(a.f[1] + b.f[3], a.f[3] + b.f[2]);
            }   
            else{
                res.f[0] = a.f[0] + b.f[0];
                res.f[1] = a.f[1] + b.f[0];
                res.f[2] = a.f[0] + b.f[2];
                res.f[3] = a.f[1] + b.f[2];
            }
            res.head = a.head;
            res.tail = b.tail;
            return res;
        }
    };
    struct SegmentTree{
        int n;
        vector<Node> tree;
        void init(int sz){
            n = sz;
            tree.resize(n * 4 + 6);
        }
        void build(int ind, int l, int r){
            if(l == r){
                tree[ind] = Node(abs(d[l]), 0, 0, 0, d[l], d[l]);
                return;
            }
            int mid = (l + r) / 2;
            build(ind * 2, l, mid);
            build(ind * 2 + 1, mid + 1, r);
            tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
        }
        void update(int ind, int l, int r, int pos, int val){
            if(l == r){
                d[l] += val;
                tree[ind] = Node(abs(d[l]), 0, 0, 0, d[l], d[l]);
                return;
            }
            int mid = (l + r) / 2;
            if(l <= pos and pos <= mid) update(ind * 2, l, mid, pos, val);
            else update(ind * 2 + 1, mid + 1, r, pos, val);
            tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
        }
        void update(int pos, int val){
            update(1, 1, n, pos, val);
        }
        int get(){
            return tree[1].f[0];
        }
    } st;
    void solve(){
        st.init(n);
        st.build(1, 1, n);
        while(q--){
            int l, r, x; cin >> l >> r >> x;
            if(l > 1) st.update(l - 1, -x);
            if(r < n) st.update(r, x);
            cout << st.get() << '\n';
        }
    }
}
void solve(){
    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]);
    }
//    if(n <= 3000){
//        sub12::solve();
//        return;
//    }
    sub3::solve();
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
}

Compilation message (stderr)

Main.cpp: In constructor 'sub3::Node::Node()':
Main.cpp:46:37: warning: '*<unknown>.sub3::Node::f[3]' is used uninitialized in this function [-Wuninitialized]
   46 |             f[0] = f[1] = f[2] = f[3];
      |                                  ~~~^

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