Submission #528228

# Submission time Handle Problem Language Result Execution time Memory
528228 2022-02-19T17:50:10 Z Falcon Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
556 ms 44624 KB
#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

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);
      |         ^~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 5 ms 848 KB Output is correct
8 Correct 5 ms 848 KB Output is correct
9 Correct 5 ms 976 KB Output is correct
10 Correct 7 ms 976 KB Output is correct
11 Correct 5 ms 964 KB Output is correct
12 Correct 5 ms 976 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 5 ms 848 KB Output is correct
8 Correct 5 ms 848 KB Output is correct
9 Correct 5 ms 976 KB Output is correct
10 Correct 7 ms 976 KB Output is correct
11 Correct 5 ms 964 KB Output is correct
12 Correct 5 ms 976 KB Output is correct
13 Correct 556 ms 43896 KB Output is correct
14 Correct 534 ms 43896 KB Output is correct
15 Correct 542 ms 43888 KB Output is correct
16 Correct 509 ms 43720 KB Output is correct
17 Correct 522 ms 43712 KB Output is correct
18 Correct 546 ms 44624 KB Output is correct