Submission #382836

#	Time	Username	Problem	Language	Result	Execution time	Memory
382836		ne4eHbKa	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	2086 ms	47084 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 2e5 + 5;
int a[N], q, n;
ll d[N];
ll f[N][3];

struct tree {
    tree *l, *r;
    ll v[3][3];
    void init(int tl) {
        memset(v, -1, sizeof v);
        v[0][0] = 0;
        ll z = d[tl];
        if(z <= 0) v[1][1] = abs(z);
        if(z >= 0) v[2][2] = abs(z);
    }
    void upd() {
        for(int i : {0, 1, 2})
        for(int j : {0, 1, 2}) {
            v[i][j] = -1;
            for(int fl : {0, 1, 2}) {
                ll &le = l->v[i][fl];
                if(le < 0) continue;
                for(int fr : {0, 1, 2}) {
                    ll &ri = r->v[fr][j];
                    if(ri < 0) continue;
                    if(fl + fr == 3) continue;
                    umax(v[i][j], le + ri);
                }
            }
        }
    }
    tree(int tl = 1, int tr = n - 1) {
        if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
            upd();
        } else {
            init(tl);
            l = r = 0;
        }
    }
    ll ans() {
        return max(f[n - 1][0], max(f[n - 1][1], f[n - 1][2]));
        ll res = 0;
        for(int i : {0, 1, 2})
            for(int j : {0, 1, 2})
                umax(res, v[i][j]);
        return res;
    }
    void reload(int i, int tl = 1, int tr = n - 1) {
        for(int i = 1; i < n; ++i) {
            for(int j : {0, 1, 2}) {
                f[i][j] = -1;
                for(int t : {0, 1, 2}) {
                    if(f[i - 1][t] < 0) continue;
                    if(t + j == 3) continue;
                    if(j == 1 && d[i] > 0) continue;
                    if(j == 2 && d[i] < 0) continue;
                    umax(f[i][j], f[i - 1][t] + abs(d[i]) * !!j);
                }
            }
        }
        return;

        if(tl == tr) return init(tl);
        int tm = tl + tr >> 1;
        i <= tm
            ? l->reload(i, tl, tm)
            : r->reload(i, tm + 1, tr);
        upd();
    }
};

void solve() {
    cin >> n >> q;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    if(n == 1) {
        while(q--) cout << "0\n";
        return;
    }
    for(int i = 1; i < n; ++i)
        d[i] = a[i] - a[i - 1];
    tree t {};
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        if(--l) {
            d[l] += x;
            t.reload(l);
        }
        if(r < n)
            d[r] -= x,
            t.reload(r);
        cout << t.ans() << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message (stderr)

Main.cpp: In constructor 'tree::tree(int, int)':
Main.cpp:63:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
Main.cpp: In member function 'void tree::reload(int, int, int)':
Main.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~

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