Submission #528228

#	Time	Username	Problem	Language	Result	Execution time	Memory
528228		Falcon	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	556 ms	44624 KiB

Main

#include <bits/stdc++.h>

#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c)        (c).begin(), (c).end()
#define rall(c)       (c).rbegin(), (c).rend()
#define rep(i, N)     for (int i = 0; i < (N); ++i)
#define rrep(i, N)    for (int i = (N)-1; i >= 0; --i)
#define rep1(i, N)    for (int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for (int i = (s); i <= (e); ++i)

#ifdef DEBUG
    #define debug(x...)                                                        \
        do {                                                                   \
            ++dbg::depth;                                                      \
            string dbg_vals = dbg::to_string(x);                               \
            --dbg::depth;                                                      \
            dbg::fprint(__func__, __LINE__, #x, dbg_vals);                     \
        } while (false)
#else
    #define debug(...) 42
#endif

template<typename T> inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T> inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

constexpr long long INF{1LL << 50};

template<typename T> class segment_tree {
private:
    int n;
    vector<T> a;

public:
    segment_tree(int n_): n{n_}, a(n << 1) {}

    segment_tree(const vector<T>& b): n{int(b.size())}, a(n << 1) {
        for (int i{}; i < n; ++i) a[i + n] = b[i];
        for (int i{n - 1}; i > 0; --i) a[i] = a[i << 1] + a[i << 1 | 1];
        debug(a);
    }

    void update(int i, const T& v) {
        a[i += n] = v;
        for (i >>= 1; i > 0; i >>= 1) a[i] = a[i << 1] + a[i << 1 | 1];
    }

    T query(int s, int e) const {
        debug(a);
        T f{}, b{};
        for (s += n, e += n; s < e; s >>= 1, e >>= 1) {
            if (s & 1) f = f + a[s++];
            if (e & 1) b = a[--e] + b;
        }
        debug(f, b);
        return f + b;
    }
};

struct node {
    bool e;
    long long f{}, l{};
    array<long long, 4> a{};

    node() { e = true; }

    node(long long v) {
        e = false;
        f = l   = v;
        a[0b00] = 0;
        a[0b01] = -INF;
        a[0b10] = -INF;
        a[0b11] = abs(v);
    }

    friend node operator+(const node& x, const node& y) {
        if (x.e) return y;
        if (y.e) return x;

        node r;
        r.f = x.f, r.l = y.l;
        r.e = false;
        if ((x.l <= 0 && y.f <= 0) || (x.l >= 0 && y.f >= 0)) {
            r.a[0b00] = max(x.a[0b00], x.a[0b01]) + max(y.a[0b00], y.a[0b10]);
            r.a[0b01] = max(x.a[0b00], x.a[0b01]) + max(y.a[0b01], y.a[0b11]);
            r.a[0b10] = max(x.a[0b10], x.a[0b11]) + max(y.a[0b00], y.a[0b10]);
            r.a[0b11] = max(x.a[0b10], x.a[0b11]) + max(y.a[0b01], y.a[0b11]);
        } else {
            r.a[0b00] = max(x.a[0b00] + max(y.a[0b00], y.a[0b10]),
                            x.a[0b01] + y.a[0b00]);
            r.a[0b01] = max(x.a[0b00] + max(y.a[0b01], y.a[0b11]),
                            x.a[0b01] + y.a[0b01]);
            r.a[0b10] = max(x.a[0b10] + max(y.a[0b00], y.a[0b10]),
                            x.a[0b11] + y.a[0b00]);
            r.a[0b11] = max(x.a[0b10] + max(y.a[0b01], y.a[0b11]),
                            x.a[0b11] + y.a[0b01]);
        }
        rep(i, 4) if (r.a[i] < 0) r.a[i] = -INF;
        return r;
    }

#ifdef DEBUG
    friend string to_string(const node& x) { return dbg::to_string(x.a); }
#endif
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    rep(i, n) cin >> a[i];
    adjacent_difference(all(a), a.begin());
    a[0] = 0;

    vector<node> b(n);
    rep(i, n) b[i] = node(a[i]);

    segment_tree<node> seg(b);

    rep(_, q) {
        int l, r;
        long long x;
        cin >> l >> r >> x;
        --l;

        a[l] += x;
        seg.update(l, node(a[l]));

        if (r < n) {
            a[r] -= x;
            seg.update(r, node(a[r]));
        }

        node k{seg.query(0, n)};
        debug(a, k.a);
        cout << max(k.a[0], k.a[1]) << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
   25 |     #define debug(...) 42
      |                        ^~
Main.cpp:142:9: note: in expansion of macro 'debug'
  142 |         debug(a, k.a);
      |         ^~~~~
Main.cpp: In instantiation of 'segment_tree<T>::segment_tree(const std::vector<_Tp>&) [with T = node]':
Main.cpp:125:29:   required from here
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
   25 |     #define debug(...) 42
      |                        ^~
Main.cpp:44:9: note: in expansion of macro 'debug'
   44 |         debug(a);
      |         ^~~~~
Main.cpp: In instantiation of 'T segment_tree<T>::query(int, int) const [with T = node]':
Main.cpp:141:30:   required from here
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
   25 |     #define debug(...) 42
      |                        ^~
Main.cpp:53:9: note: in expansion of macro 'debug'
   53 |         debug(a);
      |         ^~~~~
Main.cpp:25:24: warning: statement has no effect [-Wunused-value]
   25 |     #define debug(...) 42
      |                        ^~
Main.cpp:59:9: note: in expansion of macro 'debug'
   59 |         debug(f, b);
      |         ^~~~~

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