Submission #1016005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016005		dosts	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	322 ms	60124 KiB

Main

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define vvi vector<vi>
const int N = 4e5+1,inf = 2e18,B = 23,MOD = 998244353,LIM = 1e9;    
struct Node {
    int bas,son,yy,yn,ny,nn;
};

vi a(N),b(N);

Node merge(Node x,Node y) {
    Node ret;
    ret.bas = x.bas,ret.son = y.son;
    ret.yy = max(x.yy,x.yn)+max(y.yy,y.ny);
    ret.yn = max(x.yy,x.yn)+max(y.yn,y.nn);
    ret.ny = max(x.ny,x.nn)+max(y.ny,y.yy);
    ret.nn = max(x.nn,x.ny)+max(y.nn,y.yn);
    int d = x.son - y.bas;
    ret.yy = max(ret.yy,(x.yn+y.ny)+d);
    ret.yn = max(ret.yn,(x.yn+y.nn)+d);
    ret.ny = max(ret.ny,(x.nn+y.ny)+d);
    ret.nn = max(ret.nn,(x.nn+y.nn)+d);
    d = y.bas - x.son;
    ret.yy = max(ret.yy,(x.yy+y.yy)+d);
    ret.yn = max(ret.yn,(x.yy+y.yn)+d);
    ret.ny = max(ret.ny,(x.ny+y.yy)+d);
    ret.nn = max(ret.nn,(x.ny+y.yn)+d);
    return ret; 
}


struct ST {
    vector<Node> t;
    vi lazy;
    void build(int node,int l,int r) {
        if (l == r) {
            t[node] = {a[l],a[l],0,-inf,-inf,0};
            return;
        }
        int m = (l+r) >> 1;
        build(2*node,l,m),build(2*node+1,m+1,r);
        t[node] = merge(t[2*node],t[2*node+1]);
    }
    void push(int node,bool leaf) {
        t[node].bas+=lazy[node];
        t[node].son+=lazy[node];
        if (!leaf) {
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node] = 0;
    }
    ST(int nn) {
        t.resize(4*nn+1);
        lazy.assign(4*nn+1,0);
        build(1,1,nn);
    } 

    void update(int node,int l,int r,int L,int R,int v) {
        push(node,l==r);
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            lazy[node] += v;
            push(node,l==r);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v);
        t[node] = merge(t[2*node],t[2*node+1]);
    }
    Node query(int node,int l,int r,int L,int R) {
        push(node,l==r);
        return t[node];
    }
};
void solve() {
    int n,q;
    cin >> n >> q;
    for (int i=1;i<=n;i++) cin >> a[i];
    ST st(n);
    while (q--) {
        int l,r,v;
        cin >> l >> r >> v;
        st.update(1,1,n,l,r,v);
        Node nn = st.query(1,1,n,1,n);
        cout << max({nn.yy,nn.nn,nn.ny,nn.yn}) << '\n';
    }
}


                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #else 
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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