oj.uz

Submission #891473

# Submission time Handle Problem Language Result Execution time Memory
891473 2023-12-23T05:19:33 Z phongcd Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 324 ms 41300 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 2e5 + 2;
const int M = 31;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;

int n, q, a[N];
ll lazy[4 * N];

struct node {
    ll l, r, uu, dd, ud, du;
} st[4 * N];

node cb(node a, node b) {
    node c;
    c.l = a.l, c.r = b.r;
    ll tu = max(0ll, b.l - a.r);
    ll td = max(0ll, a.r - b.l);
    c.uu = max({a.uu + b.uu + tu, a.uu + b.du, a.ud + b.uu, a.ud + b.du + td});
    c.dd = max({a.du + b.ud + tu, a.du + b.dd, a.dd + b.ud, a.dd + b.dd + td});
    c.ud = max({a.uu + b.ud + tu, a.uu + b.dd, a.ud + b.ud, a.ud + b.dd + td});
    c.du = max({a.du + b.uu + tu, a.du + b.du, a.dd + b.uu, a.dd + b.du + td});
    return c;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id].l = st[id].r = a[l];
        st[id].ud = st[id].du = -INF;
        return ;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = cb(st[id << 1], st[id << 1 | 1]);
}

void down(int id) {
    ll t = lazy[id];
    if (!t) return ;
    st[id << 1].l += t, st[id << 1].r += t;
    st[id << 1 | 1].l += t, st[id << 1 | 1].r += t;
    lazy[id << 1] += t, lazy[id << 1 | 1] += t;
    lazy[id] = 0;
}

void upd(int id, int l, int r, int u, int v, ll w) {
    if (v < l || r < u) return ;
    if (u <= l && r <= v) {
        st[id].l += w, st[id].r += w;
        lazy[id] += w;
        return ;
    }
    down(id);
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, u, v, w);
    upd(id << 1 | 1, mid + 1, r, u, v, w);
    st[id] = cb(st[id << 1], st[id << 1 | 1]);
}

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

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

    build(1, 1, n);

    ll l, r, x;
    while (q --) {
        cin >> l >> r >> x;
        upd(1, 1, n, l, r, x);

        node res = st[1];
        ll ans =  max({res.uu, res.dd, res.ud, res.du});
        cout << ans << '\n';
    }
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 4 ms 2652 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2864 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 4 ms 2652 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2864 KB Output is correct
11 Correct 4 ms 2652 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 323 ms 40692 KB Output is correct
14 Correct 310 ms 40788 KB Output is correct
15 Correct 312 ms 41024 KB Output is correct
16 Correct 307 ms 40532 KB Output is correct
17 Correct 324 ms 40580 KB Output is correct
18 Correct 306 ms 41300 KB Output is correct