Submission #1265221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265221		g4yuhg	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	346 ms	31144 KiB

Main

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define int long long
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 500005
using namespace std;
struct Node {
    ll best, bodau, bocuoi, bo2, l, r;
} st[4 * N];
ll n, q, a[N], b[N], d[N], f2[3001][2];
Node combine(Node L, Node R) {
    Node res;
    res.l = L.l, res.r = R.r;
    res.best = max(L.bocuoi + R.best, L.best + R.bodau);
    res.bodau = max(L.bo2 + R.best, L.bodau + R.bodau);
    res.bocuoi = max(L.best + R.bo2, L.bocuoi + R.bocuoi);
    res.bo2 = max(L.bo2 + R.bocuoi, L.bodau + R.bo2);
    if (d[L.r] * d[R.l] >= 0) {
        res.best = max(L.best, L.bocuoi) + max(R.best, R.bodau);
        res.bodau = max(L.bodau, L.bo2) + max(R.best, R.bodau);
        res.bocuoi = max(L.best, L.bocuoi) + (R.bo2, R.bocuoi);
        res.bo2 = max(L.bodau, L.bo2) + max(R.bocuoi, R.bo2);
    }
    return res;
}
void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = {abs(d[l]), 0LL, 0LL, 0LL, l, r};
        return;
    }
    ll mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
}
void update(ll id, ll l, ll r, ll i, ll v) {
    if (i > r || i < l) return;
    if (l == r) {
        d[i] = v;
        st[id] = {abs(d[i]), 0LL, 0LL, 0LL, l, r};
        return;
    }
    ll mid = (l + r) / 2;
    update(id * 2, l, mid, i, v);
    update(id * 2 + 1, mid + 1, r, i, v);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
}
ll dp2(ll i, ll tt) {
    if (i >= n) {
        return 0;
    }
    if (f2[i][tt] != -1) {
        return f2[i][tt];
    }
    ll res = 0;
    if (tt == 0) { // chon hoac k chon
        //res = abs(d[i]);
        if (i + 1 <= n - 1 && d[i] * d[i + 1] < 0) {
            res = max(res, abs(d[i]) + dp2(i + 2, 0));    
            res = max(res, dp2(i + 1, 1));
        }
        else {
            res = max(res, abs(d[i]) + dp2(i + 1, 0));
        }
    }
    if (tt == 1) {
        if (i + 1 <= n - 1 && d[i] * d[i + 1] < 0) {
            res = max(res, abs(d[i]) + dp2(i + 2, 0));
        }
        else {
            res = max(res, abs(d[i]) + dp2(i + 1, 0));
        }
    }
    f2[i][tt] = res;
    return res;
}
void sub2() {
    for (int id = 1; id <= q; id ++) {
        ll l, r, x;
        cin >> l >> r >> x;
        for (int i = l; i <= r; i ++) {
            a[i] += x;
        }
        for (int i = 1; i <= n - 1; i ++) {
            d[i] = a[i] - a[i + 1];
            cout << d[i] << " ";
        }
        cout << endl;
        ll ans = 0;
        memset(f2, -1, sizeof(f2));
        ans = dp2(1, 0);
        cout << ans << endl;
    }
}
void sub3() {
    for (int i = 1; i <= n - 1; i ++) {
        d[i] = a[i] - a[i + 1];   
    }
    build(1, 1, n - 1);
    for (int i = 1; i <= q; i ++) {
        ll l, r, x;
        cin >> l >> r >> x;
        if (l - 1 > 0) update(1, 1, n - 1, l - 1, d[l - 1] - x);
        if (r) update(1, 1, n - 1, r, d[r] + x);
        cout << st[1].best << endl;
    }
}
signed main(void) {
    faster;
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    if (n <= 3000 && q <= 3000) {
        sub3();
    }
    else {
        sub3();
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55