#include <bits/stdc++.h>
using namespace std;
#define el '\n';
#define ll long long
#define fi first
#define se second
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))
template <class T1, class T2>
bool minimize(T1 &a, T2 b) {
if(a > b) {a = b; return true;} return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b) {
if(a < b) {a = b; return true;} return false;
}
const int MOD = (int)1e9 + 7;
template <class T1, class T2>
void add (T1 &a, T2 b) {
a += b;
if (a >= MOD) a -= MOD;
}
const int N = 200100;
const int oo = (int)1e9 + 7;
const ll INF = (ll)1e18 + 9LL;
const int LOG = 22;
int n, q;
long long a[N];
void init (void) {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
}
namespace subtask1 {
long long mi[222][222], ma[222][222];
long long dp[222];
void solve (void) {
while(q--) {
int l, r, x; cin >> l >> r >> x;
for (int i = l; i <= r; i++) a[i] += x;
for (int i = 1; i <= n; i++) {
mi[i][i] = a[i];
ma[i][i] = a[i];
for (int j = i + 1; j <= n; j++) {
mi[i][j] = min(mi[i][j - 1], 1LL * a[j]);
ma[i][j] = max(ma[i][j - 1], 1LL * a[j]);
}
}
for (int i = 1; i <= n; i++) {
dp[i] = ma[1][i] - mi[1][i];
// cout << dp[i] << el;
for (int j = 0; j < i; j++) {
maximize(dp[i], dp[j] + 1LL * ma[j + 1][i] - 1LL * mi[j + 1][i]);
}
}
cout << dp[n] << el;
}
}
}
namespace subtask2 {
long long dp[3333][2];
int diff[3333], pre[3333];
void solve (void) {
while(q--) {
bool isMonotonous = true;
int l, r, x; cin >> l >> r >> x;
for (int i = l; i <= r; i++) a[i] += x;
bool mark = ((a[2] - a[1]) > 0);
for (int i = 3; i <= n; i++) {
if(a[i] == a[i - 1]) continue;
bool t = ((a[i] - a[i - 1]) > 0);
if(mark != t) {
isMonotonous = false;
break;
}
}
// cout << isMonotonous;
if(!isMonotonous) {
int cur_min = a[1], cur_max = a[1];
vector <int> pre (n + 1, 0), suf (n + 1, 0);
for (int i = 1; i <= n; i++) {
maximize(cur_max, a[i]);
minimize(cur_min, a[i]);
pre[i] = cur_max - cur_min;
}
cur_min = a[n], cur_max = a[n];
for (int i = n; i >= 1; i--) {
maximize(cur_max, a[i]);
minimize(cur_min, a[i]);
suf[i] = cur_max - cur_min;
}
long long ans = 0;
for (int i = 1; i < n; i++) {
maximize(ans, pre[i] + suf[i + 1]);
}
cout << ans << el;
}
else {
for (int i = 1; i < n; i++) diff[i] = a[i] - a[i + 1];
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][0];
minimize(dp[i][1], dp[i - 1][0] + diff[i]);
maximize(dp[i][0], dp[i - 2][1]);
}
cout << min(dp[n][0], dp[n][1]) << el;
}
}
}
}
void solve (void) {
subtask2::solve();
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ntest = 1;
while(ntest--) {
init();
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
