This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL
using namespace std;
using ll = long long;
#define all(a) (a).begin(), (a).end()
void solve(){
int n, q; cin >> n >> q;
vector<ll> a(n);
for(int i=0; i<n; i++) cin >> a[i];
auto get = [&](vector<ll> a){
vector<ll> dp(n+1);
for(int i=0; i<n; i++){
ll mn=a[i], mx = a[i];
for(int j=i; j<n; j++){
mn = min(mn, a[j]);
mx = max(mx, a[j]);
dp[j+1]=max(dp[j+1], dp[i]+mx - mn);
}
}
return dp[n];
};
auto fast = [&](vector<ll> a){
vector<ll> d, dp(n+1);
for(int i=0; i+1<n; i++){
d.push_back(a[i+1] - a[i]);
}
for(int i=0; i<d.size(); i++){
// not pick
dp[i+1] = max(dp[i+1], dp[i]);
// pick
int sgn = (i+1 == d.size() ? 0 : signbit(d[i]) != signbit(d[i+1]));
dp[i+1+sgn] = max(dp[i+1+sgn], dp[i] + abs(d[i]));
}
return dp[d.size()];
};
while(q--){
ll l, r, add;
cin>>l>>r>>add;
l--, r--;
for(int i=l; i<=r;i++) a[i]+=add;
cout<<fast(a)<<endl;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t=1; //cin >> t;
while(t--) solve();
}
Compilation message (stderr)
Main.cpp: In lambda function:
Main.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0; i<d.size(); i++){
| ~^~~~~~~~~
Main.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | int sgn = (i+1 == d.size() ? 0 : signbit(d[i]) != signbit(d[i+1]));
| ~~~~^~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:19:7: warning: variable 'get' set but not used [-Wunused-but-set-variable]
19 | auto get = [&](vector<ll> a){
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |