Submission #795024

#TimeUsernameProblemLanguageResultExecution timeMemory
795024PoonYaPatSjeckanje (COCI21_sjeckanje)C++14
110 / 110
977 ms45880 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll s[1<<19][3][3],c[200005],lz[1<<19]; int n,q; void merge(int a, int b, int res) { for (int i=0; i<3; ++i) { for (int j=0; j<3; ++j) { s[res][i][j]=-1e15; for (int k=0; k<3; ++k) s[res][i][j]=max(s[res][i][j],s[a][i][k]+s[b][2-k][j]); if (i!=1) s[res][i][j]=max(s[res][i][j],s[b][i][j]); if (j!=1) s[res][i][j]=max(s[res][i][j],s[a][i][j]); } } } void push(int l, int r, int idx) { if (lz[idx]==-1e16) return; if (l!=r) { for (int i=0; i<3; ++i) { for (int j=0; j<3; ++j) { if (i==0) s[idx][i][j]-=lz[idx]; if (i==2) s[idx][i][j]+=lz[idx]; if (j==0) s[idx][i][j]-=lz[idx]; if (j==2) s[idx][i][j]+=lz[idx]; } } if (lz[2*idx]==-1e16) lz[2*idx]=lz[idx]; else lz[2*idx]+=lz[idx]; if (lz[2*idx+1]==-1e16) lz[2*idx+1]=lz[idx]; else lz[2*idx+1]+=lz[idx]; lz[idx]=-1e16; } else { c[l]+=lz[idx]; s[idx][0][0]=-1e15; s[idx][0][1]=-c[l]; s[idx][0][2]=-1e15; s[idx][1][0]=-c[l]; s[idx][1][1]=0; s[idx][1][2]=c[l]; s[idx][2][0]=-1e15; s[idx][2][1]=c[l]; s[idx][2][2]=-1e15; lz[idx]=-1e16; } } void build(int l, int r, int idx) { if (l==r) { push(l,r,idx); } else { int mid=(l+r)/2; build(l,mid,2*idx); build(mid+1,r,2*idx+1); merge(2*idx,2*idx+1,idx); } } void update(int l, int r, int idx, int x, int y, ll val) { push(l,r,idx); if (x>r || y<l) return; if (x<=l && r<=y) { lz[idx]=val; push(l,r,idx); } else { int mid=(l+r)/2; update(l,mid,2*idx,x,y,val); update(mid+1,r,2*idx+1,x,y,val); merge(2*idx,2*idx+1,idx); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); for (int i=0; i<(1<<19); ++i) for (int j=0; j<3; ++j) for (int k=0; k<3; ++k) s[i][j][k]=-1e15; for (int i=0; i<(1<<19); ++i) lz[i]=-1e16; cin>>n>>q; for (int i=1; i<=n; ++i) { int x; cin>>x; update(1,n,1,i,i,x); } while (q--) { int l,r; ll val; cin>>l>>r>>val; update(1,n,1,l,r,val); cout<<s[1][1][1]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...