Submission #891030

#	Time	Username	Problem	Language	Result	Execution time	Memory
891030		manizare	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	107 ms	36136 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5+ 10, K = 101, N = 1e6, inf = 1e18 + 1 , sq =280 , lg = 18, mod = 1e9+7 ;
int a[maxn] , val[maxn] ,n , q; 

struct node{
    int a[2][2] , f, e ; 
};
node seg[4*maxn] ;
node operator+(node a , node b){
    node res ;
    res.f=  a.f;
    res.e=  b.e; 
    rep(i , 0 , 1){
        rep(j , 0 , 1){
            res.a[i][j] = -inf ; 
            rep(k , 0 , 1){
                rep(f ,0 , 1){
                    if(a.e*b.f < 0 && f==1 && k == 1){
                        continue ;
                    }
                    res.a[i][j] = max(res.a[i][j] , a.a[i][k] + b.a[f][j]) ; 
                }
            }
        }
    }
    return res; 
}

void UPD(int x , int w , int p = 1, int l = 1, int r = n-1){
    int mid = (l+r)/2 , pl = p << 1 ,pr = p<<1 | 1 ;
    if(x > r || x < l)return ;
    if(x==l && x== r){
        rep(i,0,1)rep(j ,0 ,1)if(i+j != 2)seg[p].a[i][j] = -inf ;
        seg[p].f += w; 
        seg[p].e += w; 
        seg[p].a[1][1] = abs(seg[p].e) ;
        seg[p].a[0][0] = 0; 
        return ; 
    }
    UPD(x,w,pl,l,mid);
    UPD(x,w,pr,mid+1,r);
    seg[p] = seg[pl] + seg[pr] ;
}

void upd(int v, int w){
    val[v] +=w ; 
    UPD(v,w);
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> q ;
    rep(i , 1, n){
        cin >> a[i] ;
        if(i!=1)upd(i-1 , -a[i]) ;
        if(i!=n)upd(i , a[i]) ;
    }
    while(q--){
        int l  , r , w ;
        cin >> l >> r >> w ;
        if(l!=1){
            upd(l-1, -w) ;
        }
        if(r!=n){
            upd(r , w) ;
        }
        int ans =0 ;
        rep(i , 0 , 1)rep(j , 0 , 1)ans = max(ans , seg[1].a[i][j]) ;
        cout << ans << "\n" ;
    }
}   
/*


*/

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