Submission #873863

#	Time	Username	Problem	Language	Result	Execution time	Memory
873863		damwuan	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	289 ms	30292 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+10;
const ll N=1e5;
const ll offset=1e18;
const double eps= 1e-9;
//const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,q,a[maxn],d[maxn];
int st[maxn*4][2][2];

void Update(int u,int val,int id=1,int l=1,int r=n-1)
{
    if (l==r)
    {
        d[l]+=val;
        st[id][1][1]=abs(d[l]);
        st[id][1][0]=-inf;
        st[id][0][1]=-inf;
        st[id][0][0]=0;
        return;
    }
    int mid=l+r>>1;
    if (u<=mid) Update(u,val,id*2,l,mid);
    else Update(u,val,id*2+1,mid+1,r);
    st[id][0][0]=max({st[id*2][0][1]+st[id*2+1][0][0],st[id*2][0][0]+st[id*2+1][1][0],st[id*2][0][0]+st[id*2+1][0][0]});
    st[id][1][0]=max({st[id*2][1][1]+st[id*2+1][0][0],st[id*2][1][0]+st[id*2+1][1][0],st[id*2][1][0]+st[id*2+1][0][0]});
    st[id][0][1]=max({st[id*2][0][1]+st[id*2+1][0][1],st[id*2][0][0]+st[id*2+1][1][1],st[id*2][0][0]+st[id*2+1][0][1]});
    st[id][1][1]=max({st[id*2][1][1]+st[id*2+1][0][1],st[id*2][1][0]+st[id*2+1][1][1],st[id*2][1][0]+st[id*2+1][0][1]});
    if (d[mid]*d[mid+1]>=0)
    {
        st[id][0][0]=max(st[id][0][0],st[id*2][0][1]+st[id*2+1][1][0]);
        st[id][1][0]=max(st[id][1][0],st[id*2][1][1]+st[id*2+1][1][0]);
        st[id][0][1]=max(st[id][0][1],st[id*2][0][1]+st[id*2+1][1][1]);
        st[id][1][1]=max(st[id][1][1],st[id*2][1][1]+st[id*2+1][1][1]);
    }
}

void sol()
{
    cin >> n>> q;
    for1(i,1,n)
    {
        cin >> a[i];
    }
    for1(i,1,n-1)
    {
        Update(i,a[i+1]-a[i]);
    }
//    cerr<<max({st[1][0][0],st[1][1][0],st[1][0][1],st[1][1][1]});
    for1(i,1,q)
    {
        int l,r,x; cin >> l>>r>>x;
        if (l-1>=1) Update(l-1,x);
        if (r<n) Update(r,-x);
        cout <<max({st[1][0][0],st[1][1][0],st[1][0][1],st[1][1][1]})<<'\n';
    }

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("SUBSET.inp","r",stdin);
//    freopen("SUBSET.out","w",stdout);
    int t=1;
    //cin >> t;
    while (t--)
    {
        sol();
    }
}
/*
1 3 4
1 1
1 3
3 1
3 3
*/
/*
0 1 1 3.3
0 0 1 12.5
1 0 1 12.5
1 2 0 9.4625
2 0 0 12.5
2 0 1 13.05
3 1 0 13.2431
5 0 0 14.4931
14.493055556
*/

Compilation message (stderr)

Main.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid=l+r>>1;
      |             ~^~

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