Submission #402461

#	Time	Username	Problem	Language	Result	Execution time	Memory
402461		NintsiChkhaidze	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	847 ms	109048 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define left (node<<1),l,(l+r)>>1
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
ll sgt[4*N][5][5],a[N],b[N];
void go(int node){
    ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];
    
    for (int i=0;i<=1;i++)
        for (int j=0;j<=1;j++){
            ll m=0;
            for (int o=0;o<=1;o++)
                for (int v=0;v<=1;v++){
                    sgt[node][i][j] = sgt[(node<<1)][i][o] + sgt[((node<<1)|1)][v][j];
                    if (x*y >= 0 || o*v != 1) m = max(m,sgt[node][i][j]); 
                }
            sgt[node][i][j] = m;
        }
    sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
    sgt[node][2][0] = sgt[(node<<1)][2][0];
}
void build(int node,int l,int r){
    if (l == r){
        sgt[node][1][1] = abs(b[l]);
        sgt[node][1][0] = sgt[node][0][1] = sgt[node][0][0] = 0;
        sgt[node][2][0] = sgt[node][0][2] = b[l];
        return;
    }
    build(left),build(right);
    go(node);
}
void upd(int node,int l,int r,int ind){
    if (l == r){
        sgt[node][1][1] = abs(b[l]);
        sgt[node][1][0] = sgt[node][0][1] = sgt[node][0][0] = 0;
        sgt[node][2][0] = sgt[node][0][2] = b[l];
        return;
    }
    if (ind > ((l+r)>>1)) upd(right,ind);
    else upd(left,ind);
    go(node);
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    
    for (int i=1;i<=n;i++)
        cin>>a[i];
    
    for (int i=1;i<n;i++)
        b[i] = a[i]-a[i+1];
       
    build(1,1,n-1);
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        if (l > 1) b[l-1]-=k,upd(1,1,n-1,l-1);
        if (r < n) b[r]+=k,upd(1,1,n-1,r);
        
        ll x = max(max(sgt[1][1][1],sgt[1][0][0]),max(sgt[1][1][0],sgt[1][0][1]));
        cout<<x<<"\n";
    }
}

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