Submission #402445

#	Time	Username	Problem	Language	Result	Execution time	Memory
402445		NintsiChkhaidze	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	2093 ms	108188 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#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 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);
    ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];

    //1 1
    ll p = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][1];
    ll q = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][1];
    ll z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][1];
    ll d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][1];
    
    if(x*y < 0) d=0;
    sgt[node][1][1] = max(max(p,q),max(z,d));
    
    //1 0
    p = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][0];
    q = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][0];
    z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][0];
    d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][0];
    
    if(x*y < 0) d=0;
    sgt[node][1][0] = max(max(p,q),max(z,d));
    
    //0 1
    p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][1];
    q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][1];
    z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][1];
    d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][1];
    
    if(x*y < 0) d=0;
    sgt[node][0][1] = max(max(p,q),max(z,d));
    
    //0 0
    p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][0];
    q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][0];
    z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][0];
    d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][0];
    
    if(x*y < 0) d=0;
    sgt[node][0][0] = max(max(p,q),max(z,d));
    
    sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
    sgt[node][2][0] = sgt[(node<<1)][2][0];
}
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) upd(1,1,n-1,l-1,-k);
        //if (r < n) upd(1,1,n-1,r,k);
        if (l > 1) b[l-1]-=k;
        if (r < n) b[r]+=k;
        
        build(1,1,n-1);
        ll x = max(max(sgt[1][1][1],sgt[1][0][0]),max(sgt[1][1][0],sgt[1][0][1]));
        cout<<x<<"\n";
    }
}

Compilation message (stderr)

Main.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main (){
      | ^~~~

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