Submission #402458

#	Time	Username	Problem	Language	Result	Execution time	Memory
402458		NintsiChkhaidze	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	739 ms	115860 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];
ll get1(int node,ll x,ll y){
    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;
    return max(max(p,q),max(z,d));
}
ll get2(int node,ll x, ll y){
    ll p = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][0][0];
    ll q = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][1][0];
    ll z = sgt[(node<<1)][1][0] + sgt[((node<<1)|1)][0][0];
    ll d = sgt[(node<<1)][1][1] + sgt[((node<<1)|1)][1][0];
    
    if (x*y < 0) d=0;
    return max(max(p,q),max(z,d));
}
ll get3(int node,ll x,ll y){
    ll p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][1];
    ll q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][1];
    ll z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][1];
    ll d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][1];
    
    if(x*y < 0) d=0;
    return max(max(p,q),max(z,d));
}
ll get4(int node,ll x,ll y){
    ll p = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][1][0];
    ll q = sgt[(node<<1)][0][0] + sgt[((node<<1)|1)][0][0];
    ll z = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][0][0];
    ll d = sgt[(node<<1)][0][1] + sgt[((node<<1)|1)][1][0];
    
    if (x*y < 0) d=0;
    return max(max(p,q),max(z,d));
}
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];
    
    sgt[node][1][1] = get1(node,x,y);
    sgt[node][1][0] = get2(node,x,y);
    sgt[node][0][1] = get3(node,x,y);
    sgt[node][0][0] = get4(node,x,y);
    
    sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
    sgt[node][2][0] = sgt[(node<<1)][2][0];
    
    sgt[node][0][2] = sgt[((node<<1)|1)][0][2];
    sgt[node][2][0] = sgt[(node<<1)][2][0];
}
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);
    
    ll x = sgt[(node<<1)][0][2],y = sgt[((node<<1)|1)][2][0];
    
    sgt[node][1][1] = get1(node,x,y);
    sgt[node][1][0] = get2(node,x,y);
    sgt[node][0][1] = get3(node,x,y);
    sgt[node][0][0] = get4(node,x,y);
    
    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) 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";
    }
}

Compilation message (stderr)

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

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