Submission #382827

#	Time	Username	Problem	Language	Result	Execution time	Memory
382827		ne4eHbKa	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	2 ms	364 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][2];

struct tree {
    tree *l, *r;
    ll v[2][2];
    void init(int tl) {
        v[0][0] = 0;
        v[0][1] = -1;
        v[1][0] = -1;
        v[1][1] = abs(d[tl]);
    }
    void upd(int md) {
        bool pairable = d[md] <= 0 && d[md + 1] <= 0 ||
                        d[md] >= 0 && d[md + 1] >= 0;
        for(int i : {0, 1})
        for(int j : {0, 1}) {
            v[i][j] = -1;
            for(int fl : {0, 1}) {
                if(l->v[i][fl] < 0) continue;
                for(int fr : {0, 1}) {
                    if(r->v[fr][j] < 0) continue;
                    if(fl && fr && !pairable) continue;
                    umax(v[i][j], l->v[i][fl] + r->v[fr][j]);
                }
            }
        }
    }
    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(tm);
        } else {
            init(tl);
            l = r = 0;
        }
    }
    int ans() {
        return max(f[n - 1][0], f[n - 1][1]);
        ll res = 0;
        for(int i : {0, 1})
            for(int j : {0, 1})
                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) {
            ll fi = i ? d[i - 1] : 0;
            ll se = d[i];
            for(int j : {0, 1}) {
                f[i][j] = -1;
                for(int t : {0, 1}) {
                    if(f[i - 1][j] < 0) continue;
                    if(t && j && ((fi < 0 && se > 0) ||
                                  (fi > 0 && se < 0))) continue;
                    umax(f[i][j], f[i - 1][t] + abs(se) * 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(tm);
    }
};

void solve() {
    cin >> n >> q;
    if(n == 1) {
        while(q--) cout << "0\n";
        return;
    }
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    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 member function 'void tree::upd(int)':
Main.cpp:45:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |         bool pairable = d[md] <= 0 && d[md + 1] <= 0 ||
      |                         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In constructor 'tree::tree(int, int)':
Main.cpp:62:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |             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: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55