Submission #447849

#TimeUsernameProblemLanguageResultExecution timeMemory
447849AntekbSjeckanje (COCI21_sjeckanje)C++14
0 / 110
1 ms332 KiB
#include<bits/stdc++.h> using namespace std; const int N=1<<3; typedef long long ll; ll tab[N]; int lew[N+N], pra[N+N]; ll dp[2][2][N+N]; int red(ll a){ if(a==0)return 0; return a/abs(a); } void upd(int v){ if(v>=N){ dp[0][0][v]=dp[1][0][v]=dp[0][1][v]=0; dp[1][1][v]=abs(tab[v-N]); return; } int L=lew[v], R=pra[v], M=(L+R)>>1; int l=2*v, r=2*v+1; if(red(tab[M])*red(tab[M+1])<0){ //cout<<v<<"a\n"; for(int x=0; x<2; x++){ for(int y=0; y<2; y++){ dp[x][y][v]=0; for(int i=0; i<2; i++){ for(int j=0; j+i<2; j++){ dp[x][y][v]=max(dp[x][y][v], dp[x][i][l]+dp[j][y][r]); } } } } } else{ //cout<<v<<"b\n"; for(int x=0; x<2; x++){ for(int y=0; y<2; y++){ dp[x][y][v]=0; for(int i=0; i<2; i++){ for(int j=0; j<2; j++){ dp[x][y][v]=max(dp[x][y][v], dp[x][i][l]+dp[j][y][r]); } } } } } } void construct(){ for(int i=N; i<N+N; i++){ lew[i]=i-N; pra[i]=i-N; upd(i); } for(int i=N-1; i>0; i--){ lew[i]=lew[2*i]; pra[i]=pra[2*i+1]; upd(i); } } int n, q; void ust(int i, int x){ if(i==0 || i==n)return; tab[i]=x; i+=N; while(i>0){ upd(i); i/=2; } } void out(){ for(int i=0; i<=n; i++)cout<<tab[i]<<" "; cout<<"\n"; for(int i=1; i<N+N; i++){ cout<<i<<" "<<dp[0][0][i]<<" "<<dp[0][1][i]<<" "<<dp[1][0][i]<<" "<<dp[1][1][i]<<"\n"; } cout<<"\n"; } int main(){ cin>>n>>q; int p; cin>>p; for(int i=1; i<n; i++){ int pp; cin>>pp; tab[i]=pp-p; p=pp; } construct(); while(q--){ int l, r, d; cin>>l>>r>>d; ust(l-1, tab[l-1]+d); ust(r, tab[r]-d); //out(); cout<<max({dp[0][0][1], dp[0][1][1], dp[1][1][1], dp[1][0][1]})<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...