#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "sjeckanje"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
int n, q;
int a[300005];
namespace subtask2{
bool check(){
return n <= 3000 and q <= 3000;
}
/**
Nhan xet cua ta la ta se dung cai difference array roi dp tren do
Khi chuyen sang difference array thi ta co cac luu y:
- Cac doan duoc chon phai co cung dau.
- Cac doan duoc chon phai cach nhau 1 phan tu.
**/
int differenceArray[3003], dp[3030][2];
//dp[i][j]: cho biet day con co tong lon nhat khi xet den vi tri i va j la dang duong hay am
void update(int l, int r, int x){
differenceArray[l] += x;
differenceArray[r + 1] -= x;
}
int get(){
memset(dp, -0x3f, sizeof(dp));
dp[1][0] = dp[1][1] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 2; j++){
if (dp[i][j] > -inf){
// cout << i << ' ' << j <<' ' << dp[i][j] << endl;
if (j == 0) {
if (differenceArray[i + 1] > 0) maximize(dp[i + 1][0], dp[i][0] + differenceArray[i + 1]);
}
else {
if (differenceArray[i + 1] < 0) maximize(dp[i + 1][1], dp[i][j] - differenceArray[i + 1]);
}
maximize(dp[i + 1][0], dp[i][j]);
maximize(dp[i + 1][1], dp[i][j]);
}
}
}
return max(dp[n][0], dp[n][1]);
}
void solve(){
for(int i = 1; i <= n; i++){
cin >> a[i];
differenceArray[i] = a[i] - a[i - 1];
}
// cout << get();
for(int i = 1; i <= q; i++){
int l, r, x;
cin >> l >> r >> x;
update(l, r, x);
cout << get() << endl;
}
}
}
namespace subtask3{
bool check(){
return true;
}
/**
Ta se dua bai toan len cay segment tree
Voi 1 nut segment tree, ta se luu 2 dau.
st[nn].dp[i][j]:
**/
const int MAXN = 3e5 + 9;
int differenceArray[MAXN], a[MAXN];
struct Node{
int dp[2][2];
Node(){
memset(dp, 0, sizeof(dp));
}
} st[MAXN << 2];
Node Merge(Node a, Node b){
Node res = Node();
for(int startLeft = 0; startLeft < 2; startLeft++){
for(int endingLeft = 0; endingLeft < 2; endingLeft++){
for(int startRight = 0; startRight < 2; startRight++){
for(int endingRight = 0; endingRight < 2; endingRight++){
maximize(res.dp[startLeft][endingRight], a.dp[startLeft][endingLeft]);
maximize(res.dp[startLeft][endingRight], b.dp[startRight][endingRight]);
if (endingLeft == startRight) maximize(res.dp[startLeft][endingRight],
a.dp[startLeft][endingLeft] + b.dp[startRight][endingRight]);
}
}
}
}
return res;
}
void update(int nn, int l, int r, int pos, int val){
if (l == r){
st[nn] = Node();
if (differenceArray[l] >= 0) st[nn].dp[0][0] = differenceArray[l];
if (differenceArray[l] < 0) st[nn].dp[1][1] = -differenceArray[l];
}
else{
int mid = (l + r) >> 1;
if (pos <= mid) update(nn << 1, l, mid, pos, val);
else update(nn << 1 | 1, mid + 1, r, pos, val);
st[nn] = Merge(st[nn << 1], st[nn << 1 | 1]);
// cout << "CURNODE: " << nn << ' ' << l << ' ' << r << endl;
// for(int i = 0; i < 2; i++){
// for(int j = 0; j < 2; j++){
// cout << st[nn].dp[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
}
}
void solve(){
for(int i = 1; i <= n; i++){
cin >> a[i];
differenceArray[i] = a[i] - a[i - 1];
if (i > 1) update(1, 2, n, i, differenceArray[i]);
}
for(int i = 1; i <= q; i++){
int l, r, x;
cin >> l >> r >> x;
// cerr << l << ' ' << r << ' ' << x << endl;
differenceArray[l] += x;
differenceArray[r + 1] -= x;
// cout << l << ' ' << r + 1 << ' ' << differenceArray[l] << ' ' << differenceArray[r + 1] << endl;
if (l >= 2) update(1, 2, n, l, differenceArray[l]);
if (r + 1 <= n) update(1, 2, n, r + 1, differenceArray[r + 1]);
int mx = max({st[1].dp[0][0], st[1].dp[0][1], st[1].dp[1][0], st[1].dp[1][1]});
cout << mx << endl;
}
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> q;
// if (subtask2::check()) return subtask2::solve(), 0;
if (subtask3::check()) return subtask3::solve(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
Compilation message
Main.cpp:170:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
170 | main()
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
41560 KB |
Output is correct |
| 2 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 3 |
Correct |
4 ms |
41572 KB |
Output is correct |
| 4 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 5 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 6 |
Correct |
5 ms |
41680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
41560 KB |
Output is correct |
| 2 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 3 |
Correct |
4 ms |
41572 KB |
Output is correct |
| 4 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 5 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 6 |
Correct |
5 ms |
41680 KB |
Output is correct |
| 7 |
Correct |
9 ms |
41564 KB |
Output is correct |
| 8 |
Correct |
9 ms |
41784 KB |
Output is correct |
| 9 |
Correct |
9 ms |
41564 KB |
Output is correct |
| 10 |
Correct |
13 ms |
41560 KB |
Output is correct |
| 11 |
Correct |
9 ms |
41564 KB |
Output is correct |
| 12 |
Correct |
9 ms |
41640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
41560 KB |
Output is correct |
| 2 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 3 |
Correct |
4 ms |
41572 KB |
Output is correct |
| 4 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 5 |
Correct |
4 ms |
41564 KB |
Output is correct |
| 6 |
Correct |
5 ms |
41680 KB |
Output is correct |
| 7 |
Correct |
9 ms |
41564 KB |
Output is correct |
| 8 |
Correct |
9 ms |
41784 KB |
Output is correct |
| 9 |
Correct |
9 ms |
41564 KB |
Output is correct |
| 10 |
Correct |
13 ms |
41560 KB |
Output is correct |
| 11 |
Correct |
9 ms |
41564 KB |
Output is correct |
| 12 |
Correct |
9 ms |
41640 KB |
Output is correct |
| 13 |
Correct |
553 ms |
52816 KB |
Output is correct |
| 14 |
Correct |
561 ms |
52816 KB |
Output is correct |
| 15 |
Correct |
559 ms |
52820 KB |
Output is correct |
| 16 |
Correct |
523 ms |
52664 KB |
Output is correct |
| 17 |
Correct |
539 ms |
52584 KB |
Output is correct |
| 18 |
Correct |
508 ms |
53332 KB |
Output is correct |
