oj.uz

Submission #985931

# Submission time Handle Problem Language Result Execution time Memory
985931 2024-05-19T11:24:05 Z LOLOLO Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 863 ms 36312 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 10;
struct node{
    ll f[2][2] = {0, 0, 0, 0};
    ll st = 0, en = 0;
} seg[N * 4];

int sign(ll a) {
    if (a == 0)
        return 0;

    if (a > 0)
        return 1;

    return -1;
}

void maximize(ll &a, ll b) {
    if (a < b)
        a = b;
}

node merge(node A, node B) {
    node C;
    C.st = A.st;
    C.en = B.en;
    for (int a = 0; a < 2; a++) {
        for (int b = 0; b < 2; b++) {
            for (int c = 0; c < 2; c++) {
                for (int d = 0; d < 2; d++) {
                    if ((b & c) == 1 && sign(A.en) * sign(B.st) == 1) {
                        maximize(C.f[a][d], A.f[a][b] + B.f[c][d]);
                    }

                    if ((b & c) == 0) {
                        maximize(C.f[a][d], A.f[a][b] + B.f[c][d]);
                    }
                }
            } 
        }
    }

    return C;
}

void point(int id, int l, int r, int p, int add) {
    if (l > p || r < p)
        return;

    if (l == r) {
        seg[id].st += add;
        seg[id].en += add;
        seg[id].f[1][1] = abs(seg[id].st);
        return;
    }

    int m = (l + r) / 2;
    point(id * 2, l, m, p, add);
    point(id * 2 + 1, m + 1, r, p, add);
    seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
} 

ll a[N];

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

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i > 1) {
            point(1, 2, n, i, a[i] - a[i - 1]);
        } 
    }

    for (int i = 1; i <= q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        if (l > 1) {
            point(1, 2, n, l, x);
        }

        if (r < n) {
            point(1, 2, n, r + 1, -x);
        }

        ll ans = 0;
        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {
                maximize(ans, seg[1].f[a][b]);
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

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 344 KB Output is correct
6 Correct 1 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 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 9 ms 860 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 8 ms 1000 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 860 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 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 8 ms 860 KB Output is correct
8 Correct 9 ms 860 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 8 ms 1000 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 813 ms 35612 KB Output is correct
14 Correct 863 ms 35936 KB Output is correct
15 Correct 811 ms 35664 KB Output is correct
16 Correct 800 ms 35616 KB Output is correct
17 Correct 793 ms 35616 KB Output is correct
18 Correct 769 ms 36312 KB Output is correct