Submission #956176

#	Time	Username	Problem	Language	Result	Execution time	Memory
956176		GHuy	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	2648 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define node pair<ll,ll>
#define oo (ll)(1e18)
#define mod (ll)(1e9+7)
#define CJD (ll)(2e6+10)
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
struct kt
{
    ll maxx=0,minn=0,ans=0;
};
kt IT[CJD*4];
ll n,q,lazy[CJD*4];
void upd(ll g,ll ls,ll rs,ll l,ll r,ll val)
{
    if(lazy[g]!=0)
    {
        IT[g].maxx+=lazy[g];
        IT[g].minn+=lazy[g];
        if(ls!=rs)
        {
            lazy[g*2]+=lazy[g];
            lazy[g*2+1]+=lazy[g];
        }
        lazy[g]=0;
    }
    if(l>rs||ls>r)return;
    if(l<=ls&&rs<=r)
    {
        IT[g].maxx+=val;
        IT[g].minn+=val;
        if(ls!=rs)
        {
            lazy[g*2]+=val;
            lazy[g*2+1]+=val;
        }
        return;
    }
    ll mid=(ls+rs)/2;
    upd(g*2,ls,mid,l,r,val);
    upd(g*2+1,mid+1,rs,l,r,val);
    IT[g].maxx=max(IT[g*2].maxx,IT[g*2+1].maxx);
    IT[g].minn=min(IT[g*2].minn,IT[g*2+1].minn);
    IT[g].ans=max(IT[g*2].ans+IT[g*2+1].ans,IT[g].maxx-IT[g].minn);
}
signed main()
{
//    freopen("centroid12.in","r",stdin);
//    freopen("centroid12.out","w",stdout);
    FAST;
    cin >> n >> q;
    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin >> x;
        upd(1ll,1ll,n,i,i,x);
    }
    while(q--)
    {
        ll l,r,x;
        cin >> l >> r >> x;
        upd(1ll,1ll,n,l,r,x);
        cout << IT[1].ans << "\n";
    }
}
/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1

*/

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