Submission #1116399

#TimeUsernameProblemLanguageResultExecution timeMemory
1116399staszic_ojuzFoehn Phenomena (JOI17_foehn_phenomena)C++17
0 / 100
210 ms13128 KiB
#include <iostream> using namespace std; long long tree[800'007]; void UpdateTree(long long v, long long l, long long r, long long vl, long long vr, long long val){ if (vl>r||vr<l) return; if (vl>=l&&vr<=r){ tree[v]+=val; return; } long long mid=(vl+vr)/2; UpdateTree(2*v, l, r, vl, mid, val); UpdateTree(2*v+1, l, r, mid+1, vr, val); } long long GetTree(long long v){ long long out=0; while (v>0){ out+=tree[v]; v>>=1; } return out; } long long temps[800'007]; void UpdateTemps(long long v, long long l, long long r, long long vl, long long vr, long long val){ if (vl>r||vr<l) return; if (vl>=l&&vr<=r){ temps[v]+=val; return; } long long mid=(vl+vr)/2; UpdateTemps(2*v, l, r, vl, mid, val); UpdateTemps(2*v+1, l, r, mid+1, vr, val); } long long GetTemps(long long v){ long long out=0; while (v>0){ out+=temps[v]; v>>=1; } return out; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); for (long long i=0;i<400'007;i++) tree[i]=0; for (long long i=0;i<400'007;i++) temps[i]=0; long long n, q, s, t; cin>>n>>q>>s>>t; long long trsize=1; while (trsize<n+1) trsize<<=1; for (long long i=0;i<=n;i++){ cin>>tree[trsize+i]; } for (long long i=1;i<n+1;i++){ temps[trsize+i]=temps[trsize+i-1]; if (tree[trsize+i]>tree[trsize+i-1]) temps[trsize+i]-=s*(tree[trsize+i]-tree[trsize+i-1]); else temps[trsize+i]+=t*(tree[trsize+i-1]-tree[trsize+i]); } // for (long long i=trsize;i<2*trsize;i++) cout<<GetTemps(i)<<" "; // cout<<'\n'; for (long long qe=0;qe<q;qe++){ long long l, r, x; cin>>l>>r>>x; UpdateTree(1, trsize+l, trsize+r, trsize, 2*trsize-1, x); if (l>0){ long long preBorder=GetTree(trsize+l-1), postBorder=GetTree(trsize+l); if (preBorder>=postBorder&&preBorder>=postBorder-x){ UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, -t*x); } else if (preBorder<postBorder&&preBorder<postBorder-x){ UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, -s*x); } else if (preBorder<postBorder&&preBorder>=postBorder-x){ UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, -t*(preBorder-postBorder+x)+(-s)*(postBorder-preBorder)); } else{ UpdateTemps(1, trsize+l, 2*trsize-1, trsize, 2*trsize-1, s*(postBorder-x-preBorder)+t*(postBorder-preBorder)); } } if (r<n){ long long preBorder=GetTree(trsize+r), postBorder=GetTree(trsize+r+1); if (preBorder>=postBorder&&preBorder-x>=postBorder){ UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, t*x); } else if (preBorder<postBorder&&preBorder-x<postBorder){ UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, s*x); } else if (preBorder<postBorder&&preBorder-x>=postBorder){ UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, -t*(preBorder-x-postBorder)+s*(postBorder-preBorder)); } else{ UpdateTemps(1, trsize+r+1, 2*trsize-1, trsize, 2*trsize-1, s*(postBorder-preBorder+x)-t*(preBorder-postBorder)); } } // for (long long i=trsize;i<trsize+n+1;i++) cout<<GetTree(i)<<" "; // cout<<'\n'; // for (long long i=trsize;i<trsize+n+1;i++) cout<<GetTemps(i)<<" "; // cout<<'\n'; cout<<GetTemps(trsize+n)<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...