제출 #870942

#제출 시각아이디문제언어결과실행 시간메모리
870942Ahmed57Sjeckanje (COCI21_sjeckanje)C++17
110 / 110
822 ms38476 KiB
#include <bits/stdc++.h> using namespace std; #define int long long struct node{ int borders[2] , dp[2][2]; }seg[800001]; node combine(node a ,node b){ node res; res.borders[0] = a.borders[0]; res.borders[1] = b.borders[1]; for(int i = 0;i<2;i++)for(int j = 0;j<2;j++)res.dp[i][j] = 0; for(int l = 0;l<2;l++){ for(int m = 0;m<2;m++){ for(int o = 0;o<2;o++){ for(int r = 0;r<2;r++){ if(m&o){ if((a.borders[1]<0)==(b.borders[0]<0)){ res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]); } }else{ res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]); } } } } } return res; } int arr[200001]; void build(int p,int l,int r){ if(l==r){ seg[p].borders[0] = seg[p].borders[1] = arr[l]; seg[p].dp[0][0] = 0; seg[p].dp[0][1] = 0; seg[p].dp[1][0] = 0; seg[p].dp[1][1] = abs(arr[l]); return ; } int md = (l+r)/2; build(p*2,l,md); build(p*2+1,md+1,r); seg[p] = combine(seg[p*2],seg[p*2+1]); } void update(int p,int l,int r,int idx){ if(l==r){ seg[p].borders[0] = seg[p].borders[1] = arr[l]; seg[p].dp[0][0] = 0; seg[p].dp[0][1] = 0; seg[p].dp[1][0] = 0; seg[p].dp[1][1] = abs(arr[l]); return ; } int md = (l+r)/2; if(idx<=md)update(p*2,l,md,idx); else update(p*2+1,md+1,r,idx); seg[p] = combine(seg[p*2],seg[p*2+1]); } signed main(){ ios_base::sync_with_stdio(false);cin.tie(0); int n,q; cin>>n>>q; int vl[n+1]; for(int i = 1;i<=n;i++)cin>>vl[i]; for(int i = 1;i<n;i++){ arr[i] = vl[i+1]-vl[i]; } build(1,1,n-1); while(q--){ int l,r,x;cin>>l>>r>>x; if(l>1){ arr[l-1]+=x; update(1,1,n-1,l-1); }if(r<n){ arr[r]-=x; update(1,1,n-1,r); } cout<<max({seg[1].dp[0][0],seg[1].dp[1][0],seg[1].dp[0][1],seg[1].dp[1][1]})<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...