Submission #992922

#	Time	Username	Problem	Language	Result	Execution time	Memory
992922		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	513 ms	73684 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define faster ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
const int N = 2e5 + 5,inf = 1e16;
int tree[4*N][3][3];
int lazy[4*N];
int n,q;
int a[N];
void build(int id,int dau,int cuoi){
    if(dau == cuoi){
        tree[id][0][0] = 0;
        tree[id][0][1] = -a[dau];
        tree[id][0][2] = a[dau];
        tree[id][1][0] = -a[dau];
        tree[id][2][0] = a[dau];
        return;
    }
    int giua = (dau + cuoi)/2;
    build(id*2,dau,giua);
    build(id*2+1,giua+1,cuoi);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            tree[id][i][j] = max({tree[id*2][i][j],tree[id*2+1][i][j],tree[id*2][i][0] + tree[id*2+1][0][j],tree[id*2][i][1] + tree[id*2+1][2][j],tree[id*2][i][2] + tree[id*2+1][1][j]});
        }
    }
}
void day(int id){
    int val = lazy[id] ;
    lazy[id] = 0;
    lazy[id*2] += val;
    lazy[id*2+1] += val;
    tree[id*2][0][1] -= val;
    tree[id*2][1][0] -= val;
    tree[id*2][0][2] += val;
    tree[id*2][2][0] += val;
    tree[id*2][1][1] -= val*2;
    tree[id*2][2][2] += val*2;
    tree[id*2+1][0][1] -= val;
    tree[id*2+1][1][0] -= val;
    tree[id*2+1][0][2] += val;
    tree[id*2+1][2][0] += val;
    tree[id*2+1][1][1] -= val*2;
    tree[id*2+1][2][2] += val*2;
}
void up(int id,int dau,int cuoi,int l,int r,int val){
    if(dau > r || cuoi < l) return ;
    if(l <= dau && cuoi <= r){
        tree[id][0][1] -= val;
        tree[id][1][0] -= val;
        tree[id][0][2] += val;
        tree[id][2][0] += val;
        tree[id][1][1] -= val*2;
        tree[id][2][2] += val*2;
        lazy[id] += val;
        return;
    }
    int giua = (dau + cuoi)/2;
    day(id);
    up(id*2,dau,giua,l,r,val);
    up(id*2+1,giua+1,cuoi,l,r,val);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            tree[id][i][j] = max({tree[id*2][i][j],tree[id*2+1][i][j],tree[id*2][i][0] + tree[id*2+1][0][j],tree[id*2][i][1] + tree[id*2+1][2][j],tree[id*2][i][2] + tree[id*2+1][1][j]});
        }
    }
}
signed main(){
    faster
    cin>> n>> q;
    for(int i = 1; i <= n; i++){
        cin>> a[i];
    }
    for(int i = 1;i <= 4*n; i++){
        for(int j = 0; j < 3; j++){
            for(int x = 0; x < 3; x++){
                tree[i][j][x] = -inf;
            }
        }
    }
    build(1,1,n);

    while(q--){
        int l,r,x;
        cin>> l>> r>> x;
        up(1,1,n,l,r,x);
        cout<<tree[1][0][0]<<endl;
    }

}

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