oj.uz

Submission #861744

# Submission time Handle Problem Language Result Execution time Memory
861744 2023-10-16T22:56:06 Z dbence Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 332 ms 39956 KB 
#include <bits/stdc++.h>
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
using namespace std;
typedef long long ll;
const ll N = 2e5 + 1;
ll n, q, current, arr[N], dif[N], dp[N];

bool difsign(ll x, ll y) {
    return (x >= 0) != (y >= 0);
}

struct Node {
    ll l, r;
    ll pre, ans, suf, ins;

    Node operator + (const Node &node) const {
        Node result;
        result.l = l;
        result.r = node.r;
        result.ans = result.pre = result.suf = result.ins = 0;
        result.ans = max(result.ans, pre + node.ans);
        result.ans = max(result.ans, ans + node.suf);
        result.pre = max(result.pre, ans + node.ins);
        result.pre = max(result.pre, pre + node.pre);
        result.suf = max(result.suf, ins + node.ans);
        result.suf = max(result.suf, suf + node.suf);
        result.ins = max(result.ins, suf + node.ins);
        result.ins = max(result.ins, ins + node.pre);
        if (!difsign(dif[r], dif[node.l])) {
            result.ans = max(result.ans, ans + node.ans);
            result.pre = max(result.pre, ans + node.pre);
            result.suf = max(result.suf, suf + node.ans);
            result.ins = max(result.ins, suf + node.pre);
        }
        return result;
    }
} node[N << 2];

void merge(ll id, ll l, ll r) {
    node[id] = node[l] + node[r];
}

void init(ll id) {
    node[id].ans = abs(dif[node[id].l]);
    node[id].pre = 0;
    node[id].suf = 0;
    node[id].ins = 0;
}

void build(ll id, ll l, ll r) {
    node[id].l = l;
    node[id].r = r;
    if (l == r) {
        init(id);
        return;
    }
    ll q = l + r >> 1;
    build(l(id), l, q);
    build(r(id), q + 1, r);
    merge(id, l(id), r(id));
}

void update(ll id, ll i, ll x) {
    if (node[id].l == node[id].r) {
        dif[i] += x;
        init(id);
        return;
    }
    ll q = node[id].l + node[id].r >> 1;
    if (i <= q) {
        update(l(id), i, x);
    } else {
        update(r(id), i, x);
    }
    merge(id, l(id), r(id));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    for (ll i = 1; i < n; ++i) {
        dif[i] = arr[i + 1] - arr[i];
    }
    build(0, 1, n - 1);
    for (ll i = 0; i < q; ++i) {
        ll l, r, x;
        cin >> l >> r >> x;
        
        if (l > 1)
            update(0, l - 1, x);
        if (r < n)
            update(0, r, -x);
        
        cout << node[0].ans << "\n";
    }
}

Compilation message

Main.cpp: In function 'void build(ll, ll, ll)':
Main.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     ll q = l + r >> 1;
      |            ~~^~~
Main.cpp: In function 'void update(ll, ll, ll)':
Main.cpp:70:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     ll q = node[id].l + node[id].r >> 1;
      |            ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4456 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4456 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 4 ms 6748 KB Output is correct
11 Correct 4 ms 6748 KB Output is correct
12 Correct 3 ms 6704 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4456 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 4 ms 6748 KB Output is correct
10 Correct 4 ms 6748 KB Output is correct
11 Correct 4 ms 6748 KB Output is correct
12 Correct 3 ms 6704 KB Output is correct
13 Correct 319 ms 39348 KB Output is correct
14 Correct 332 ms 39612 KB Output is correct
15 Correct 321 ms 39504 KB Output is correct
16 Correct 324 ms 39300 KB Output is correct
17 Correct 304 ms 39252 KB Output is correct
18 Correct 321 ms 39956 KB Output is correct