Submission #868154

#	Time	Username	Problem	Language	Result	Execution time	Memory
868154		wakandaaa	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	658 ms	67924 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file "sjeckanje"

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, q;
int a[N];

namespace sub_n2 {

int f[N][2];

void solve() {
    while (q--) {
        int l, r, c;
        cin >> l >> r >> c;
        for (int i = l; i <= r; ++i) a[i] += c;
        for (int i = 0; i <= n; ++i) for (int j = 0; j < 2; ++j) f[i][j] = -ooo;
        f[1][0] = f[1][1] = 0;
        for (int i = 1; i < n; ++i) for (int j = 0; j < 2; ++j) {
            if (f[i][j] == -ooo) continue;
            if (j == 0) {
                if (a[i] < a[i + 1]) maxi(f[i + 1][0], f[i][j] + a[i + 1] - a[i]);
            }
            if (j == 1) {
                if (a[i] > a[i + 1]) maxi(f[i + 1][1], f[i][j] + a[i] - a[i + 1]);
            }
            maxi(f[i + 1][0], f[i][j]);
            maxi(f[i + 1][1], f[i][j]);
        }
        cout << max(f[n][0], f[n][1]) << '\n';
    }
}

}

struct node {
    int l, r;
    int f[2][2];
    node() {
        for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) f[i][j] = -ooo;
    }
    int get() {
        return max({f[0][0], f[0][1], f[1][0], f[1][1]});
    }
};

node t[N];
int lazy[N];

node unite(const node &x, const node &y) {
    node res;
    res.l = x.l, res.r = y.r;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) for (int l = 0; l < 2; ++l) if (x.f[i][j] != -ooo && y.f[k][l] != -ooo) {
        int val = x.f[i][j] + y.f[k][l];
        if (j == k) {
            if (j == 0) {
                if (x.r < y.l) val += y.l - x.r;
            } else {
                if (x.r > y.l) val += x.r - y.l;
            }
        }
        maxi(res.f[i][l], val);
    }
    return res;
}
void build(int i, int L, int R) {
    if (L == R) {
        t[i].l = t[i].r = a[L];
        t[i].f[0][0] = t[i].f[1][1] = 0;
        return;
    }
    int M = (L + R) >> 1;
    build(i << 1, L, M);
    build(i << 1 | 1, M + 1, R);
    t[i] = unite(t[i << 1], t[i << 1 | 1]);
}
void down(int i) {
    for (int j = i * 2; j <= i * 2 + 1; ++j) {
        t[j].l += lazy[i];
        t[j].r += lazy[i];
        lazy[j] += lazy[i];
    }
    lazy[i] = 0;
}
void update(int i, int L, int R, int l, int r, int c) {
    if (r < L || l > R) return;
    if (l <= L && R <= r) {
        t[i].l += c;
        t[i].r += c;
        lazy[i] += c;
        return;
    }
    down(i);
    int M = (L + R) >> 1;
    update(i << 1, L, M, l, r, c);
    update(i << 1 | 1, M + 1, R, l, r, c);
    t[i] = unite(t[i << 1], t[i << 1 | 1]);
}
void update(int l, int r, int c) {
    update(1, 1, n, l, r, c);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    build(1, 1, n);
    
    while (q--) {
        int l, r, c;
        cin >> l >> r >> c;
        update(l, r, c);
        cout << t[1].get() << '\n';
    }

    return 0;
}

/*

*/

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