Submission #912401

#TimeUsernameProblemLanguageResultExecution timeMemory
912401Trisanu_DasSjeckanje (COCI21_sjeckanje)C++17
110 / 110
459 ms28820 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int T[800100][2][2], arr[200100]; void merge(int n, int mid) { for (int i=0;i<2;i++) for (int j=0;j<2;j++) { T[n][i][j]=-1e18; for (int k=0;k<2;k++) for (int l=0;l<2;l++) if (l!=1||k!=1||arr[mid]*arr[mid+1]>=0) T[n][i][j]=max(T[n][i][j],T[n*2][i][k]+T[n*2+1][l][j]); } } void upd(int p,int l,int r,int pos) { if (l==r) { T[p][1][1]=abs(arr[l]); return; } int mid=l+r>>1; if (pos<=mid) upd(p*2,l,mid,pos); else upd(p*2+1,mid+1,r,pos); merge(p,mid); } signed main() { cin.sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; for(int i = 1; i <= n; i++) cin >> arr[i]; for(int i = n; --i;) arr[i+1]-=arr[i], upd(1,1,n,i+1); arr[1]=0; for(int i = 0; i < q; i++) { int l, r, x; cin >> l >> r >> x; if(l!=1) arr[l]+=x, upd(1,1,n,l); if(r!=n) arr[r+1]-=x, upd(1,1,n,r+1); cout << max(max(T[1][0][0],T[1][0][1]),max(T[1][1][0],T[1][1][1])) << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
Main.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=l+r>>1;
      |          ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...