oj.uz

Submission #1062021

# Submission time Handle Problem Language Result Execution time Memory
1062021 2024-08-16T17:13:25 Z PanosPask Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1389 ms 119016 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

struct SegTree {
    struct Node {
        /* ans[l][r]:
         * The maximum answer for this segment
         *
         * l and r are boolean variables denoting if we include the leftmost and rightmost elements
         * respectively
         */
        vector<vector<ll>> ans;

        vector<ll> sign;

        Node(void) {
            ans.assign(2, vector<ll>(2, 0));
            sign.assign(2, 0);
        }
    };

    Node DEFAULT;
    int size;
    vector<Node> tree;

    Node merge(const Node& a, const Node& b)
    {
        Node res;

        res.sign[0] = a.sign[0];
        res.sign[1] = b.sign[1];
        if (a.sign[1] == b.sign[0] || a.sign[1] == 0 || b.sign[0] == 0) {
            // We can merge

            for (int l = 0; l < 2; l++) {
                for (int r = 0; r < 2; r++) {
                    res.ans[l][r] = a.ans[l][1] + b.ans[1][r];
                }
            }
        }
        else {
            for (int l = 0; l < 2; l++) {
                for (int r = 0; r < 2; r++) {
                    res.ans[l][r] = max(a.ans[l][1] + b.ans[0][r], a.ans[l][0] + b.ans[1][r]);
                }
            }
        }

        return res;
    }

    int val(int v) {
        if (v < 0) {
            return -1;
        }
        if (v > 0) {
            return 1;
        }

        return 0;
    }

    void init(int N) {
        size = 1;
        while (size < N) {
            size *= 2;
        }

        tree.assign(2 * size, Node());
    }

    void build(vector<ll>& a, int x, int lx, int rx) {
        if (lx == rx - 1) {
            if (lx < a.size()) {
                tree[x].ans[1][1] = abs(a[lx]);
                tree[x].sign[0] = tree[x].sign[1] = val(a[lx]);
            }

            return;
        }

        int mid = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, mid);
        build(a, 2 * x + 2, mid, rx);

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void build(vector<ll>& a) {
        return build(a, 0, 0, size);
    }

    void set(int i, ll v, int x, int lx, int rx) {
        if (lx == rx - 1) {
            tree[x].ans[1][1] = abs(v);
            tree[x].sign[0] = tree[x].sign[1] = val(v);
            return;
        }

        int mid = (lx + rx) / 2;
        if (i < mid) {
            set(i, v, 2 * x + 1, lx, mid);
        }
        else {
            set(i, v, 2 * x + 2, mid, rx);
        }

        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void set(int i, ll v) {
        set(i, v, 0, 0, size);
    }

    ll calc(int l, int r) {
        return tree[0].ans[1][1];
    }
};

int N, Q;
SegTree st;
vector<int> A;
vector<ll> D;

int main(void)
{
    scanf("%d %d", &N, &Q);

    A.resize(N);
    st.init(N - 1);
    D.resize(N - 1);

    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for (int i = 0; i < N - 1; i++) {
        D[i] = A[i + 1] - A[i];
    }
    st.build(D);

    while (Q--) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        l--; l--;
        r--;

        if (l >= 0) {
            D[l] += x;
            st.set(l, D[l]);
        }
        if (r < N - 1) {
            D[r] -= x;
            st.set(r, D[r]);
        }

        printf("%lld\n", st.calc(0, N - 1));
    }

    return 0;
}

Compilation message

Main.cpp: In member function 'void SegTree::build(std::vector<long long int>&, int, int, int)':
Main.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             if (lx < a.size()) {
      |                 ~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     scanf("%d %d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         scanf("%d %d %d", &l, &r, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 10 ms 2140 KB Output is correct
8 Correct 10 ms 2264 KB Output is correct
9 Correct 10 ms 2140 KB Output is correct
10 Correct 10 ms 2140 KB Output is correct
11 Correct 10 ms 2140 KB Output is correct
12 Correct 10 ms 2240 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 10 ms 2140 KB Output is correct
8 Correct 10 ms 2264 KB Output is correct
9 Correct 10 ms 2140 KB Output is correct
10 Correct 10 ms 2140 KB Output is correct
11 Correct 10 ms 2140 KB Output is correct
12 Correct 10 ms 2240 KB Output is correct
13 Correct 1366 ms 115800 KB Output is correct
14 Correct 1389 ms 118604 KB Output is correct
15 Correct 1337 ms 118556 KB Output is correct
16 Correct 1343 ms 118432 KB Output is correct
17 Correct 1319 ms 118352 KB Output is correct
18 Correct 1337 ms 119016 KB Output is correct