Submission #1149676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149676		imarn	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	320 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=2e5+5;
struct node{
    ll dp[3][3];
    node operator+(node b){
        node rs;
        if(dp[0][0]==-1)return b;
        if(b.dp[0][0]==-1)return (rs=*this);
        rs.dp[0][0] = max({dp[0][0]+b.dp[0][0],dp[0][1]+b.dp[0][2],dp[0][2]+b.dp[0][1]});
        rs.dp[0][1] = max({dp[0][1]+b.dp[0][0],dp[0][0]+b.dp[0][1],dp[1][1]+b.dp[0][2],dp[0][2]+b.dp[1][1]});
        rs.dp[0][2] = max({dp[0][2]+b.dp[0][0],dp[0][0]+b.dp[0][2],dp[2][2]+b.dp[0][1],dp[0][1]+b.dp[2][2]});
        rs.dp[1][1] = max({dp[1][1]+b.dp[0][0],dp[0][1]+b.dp[0][1],dp[0][0]+b.dp[1][1]});
        rs.dp[2][2] = max({dp[2][2]+b.dp[0][0],dp[0][0]+b.dp[2][2],dp[0][2]+b.dp[0][2]});
        return rs;
    }
}t[4*mxn];ll a[mxn],lz[4*mxn];
void build(int i,int l,int r){
    if(l==r){
        t[i].dp[0][0]=0;
        t[i].dp[0][1]=a[l];
        t[i].dp[0][2]=-a[l];
        t[i].dp[1][1]=-1e10;
        t[i].dp[2][2]=-1e10;
        return;
    }
    int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
void push(int i,int l,int r){
    t[i].dp[0][1]+=lz[i];
    t[i].dp[0][2]-=lz[i];
    if(l!=r)t[i].dp[1][1]+=2*lz[i],t[i].dp[2][2]-=2*lz[i];
    if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
    lz[i]=0;
}
void update(int i,int l,int r,int tl,int tr,int v){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]+=v;push(i,l,r);return;
    }int m=(l+r)>>1;
    update(2*i,l,m,tl,tr,v);
    update(2*i+1,m+1,r,tl,tr,v);
    t[i]=t[2*i]+t[2*i+1];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        update(1,1,n,l,r,x);
        cout<<t[1].dp[0][0]<<'\n';
    }
}

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