Submission #891031

#TimeUsernameProblemLanguageResultExecution timeMemory
891031manizareSjeckanje (COCI21_sjeckanje)C++14
110 / 110
573 ms38288 KiB
#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 = 2e5+ 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" ; } } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...