Submission #922275

#	Time	Username	Problem	Language	Result	Execution time	Memory
922275		Github	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	943 ms	49320 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <stack>
#include <set>
#include <sstream>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const ll INF = 1e9;

struct node{
    ll corner[2];
    ll dp[2][2];
};

node null = {0, 0, 0, 0, 0, 0};
class SegmentTree{
private:
    int n;
    vector<node> st;
public:
    SegmentTree(int m){
        n = m;
        st.resize(4*n, null);
    }

    node combine(node a, node b){
        node p = null;
        p.corner[0] = a.corner[0];
        p.corner[1] = b.corner[1];
        for (int l = 0; l < 2; l++){
            for (int s = 0; s < 2; s++){
                for (int t= 0; t < 2; t++){
                    for (int r = 0; r < 2; r++){
                        if (s && t){
                            if (a.corner[1]*b.corner[0] > 0){
                                p.dp[l][r] = max(p.dp[l][r], a.dp[l][s]+b.dp[t][r]);
                            }
                        }else{
                            p.dp[l][r] = max(p.dp[l][r], a.dp[l][s]+b.dp[t][r]);
                        }
                    }
                }
            }
        }
        return p;
    }

    void update(int p, int L, int R, int idx, ll x){
        if (L == R){
            st[p].corner[0] += x;
            st[p].corner[1] += x;
            st[p].dp[1][1] = abs(st[p].corner[0]);
            return;
        }
        int m = (L+R)/2;
        if (idx <= m){
            update(2*p, L, m,  idx, x);
        }else{
            update(2*p+1, m+1, R , idx, x);
        }
        st[p] = combine(st[2*p], st[2*p+1]);
    }

    node query(int p, int L, int R, int l, int r){
        if (l <= L && R <= r){
            return st[p];
        }
        if (R < l || L > r){
            return null;
        }
        int m = (L+R)/2;
        return combine(query(2*p, L, m, l, r), query(2*p+1, m+1, R, l, r));
    }
};

int main(){
    speedup
    int n, q; cin >> n >> q;
    SegmentTree T(n-1);
    ll prev = 0, cur;
    vector<ll> a(n);
    for (int i = 0; i < n; i++){
        cin >> cur;
        a[i] = cur;
        if (i){
            T.update(1, 0, n-2, i-1, cur-prev);
        }
        prev = cur;
    }
    for (int i = 0; i < q; i++){
        int l, r; cin >> l >> r; ll x; cin >> x;
        l--,r--;
        if (l >= 1){
            T.update(1, 0, n-2, l-1, x);
        }
        if (r < n-1) {
            T.update(1, 0, n - 2, r, -x);
        }
        cout << T.query(1, 0, n-2, 0, n-2).dp[1][1] << endl;
    }
    return 0;
}

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